K-th String

source: Osaka University Programming Contest 2013

raw_problem:
K-th String

Problem Statement

長さ<var>N</var>の文字列<var>S</var>に対する接尾辞配列<var>SA</var>を，以下の手順で得られる<var>N</var>以下の正整数の順列として定義する．

<var>S</var>の<var>i</var>文字目から<var>j</var>文字目までの部分文字列を<var>S[i..j]</var>と表す．ただし添字は1-indexedである．

各接尾辞<var>S[i..N] (i=1,2,...,N)</var>を辞書式順序（昇順）で整列する．

整列した各接尾辞の開始位置<var>i</var>を順に並べる．

たとえば，<var>S</var>="mississippi"の接尾辞配列<var>SA</var>は，以下のようになる．

入力として，長さ<var>N</var>の文字列に対する接尾辞配列<var>SA</var>が与えられる．

<var>SA</var>が得られるような文字列のうち，辞書式順序で<var>K</var>番目(1-indexed)のものを求めよ．

ただし，元の文字列は，アルファベット順に'a'から数えて高々<var>A</var>個の文字のみからなる．

Input

入力は以下の形式に従う．与えられる数は全て整数である．

<var>N</var> <var>A</var> <var>K</var>
<var>SA_1</var>
<var>SA_2</var>
...
<var>SA_N</var>

Constraints

<var>1≦N≦10^5</var>

<var>1≦A≦26</var>

<var>1≦K≦10^{18}</var>

<var>1≦SA_i≦N</var>

<var>i \neq j</var> ならば <var>SA_i \neq SA_j</var>

Output

<var>SA</var>が得られるような辞書式順序で<var>K</var>番目の文字列を1行に出力せよ．

<var>K</var>番目の文字列が存在しない場合，"Impossible"と出力せよ．

Sample Input 1

3 4 2
2
1
3

Output for the Sample Input 1

bad

<var>A</var>=4の場合，<var>SA</var>={2,1,3}となる文字列は"bac","bad","cad","cbd"の4通り．

したがって，辞書式順序で2番目の"bad"が答えとなる．

Sample Input 2

18 26 10275802967
10
14
9
13
7
8
2
6
11
18
12
1
4
3
16
5
17
15

Output for the Sample Input 2

ritsumeicampdaytwo

source: aizu

question:
K-th String
Problem Statement
Consider a suffix array $SA$ for a string $S$ of length $N$, which can be defined as a permutation of positive integers not greater than $N$, obtained by the following procedure:
We denote the substring of $S$ from its $i-th$ to $j-th$ character as $S[i..j]$. Note that the indices are 1-indexed.
- Sort each suffix $S[i..N] (i=1,2,...,N)$ in lexicographical order (ascending).
- Arrange the starting positions $i$ of the sorted suffixes in order.
For example, the suffix array $SA$ for $S$="mississippi" becomes as follows:
![image](1.png)

As input, a suffix array $SA$ for a string of length $N$ is given.
Find the $K-th$ lexicographically smallest string (1-indexed) among the strings that can yield the given $SA$.
Note that the original string consists of only up to $A$ different characters in alphabetical order, starting from 'a'.
Input
The input follows the format below, where all the provided numbers are integers.
$N$ $A$ $K$

$SA_1$

$SA_2$
...

$SA_N$
Constraints
- $1 \le N \le 10^5$
- $1 \le A \le 26$
- $1 \le K \le 10^{18}$
- $1 \le SA_i \le N$
- If $i \neq j$ then $SA_i \neq SA_j$
Output
Output the $K-th$ lexicographical string corresponding to $SA$ on a single line.
If the $K-th$ string does not exist, output "Impossible".
Sample Input 1
3 4 2
2
1
3

Output for the Sample Input 1
bad
When $A$=4, there are four strings that produce $SA$={2,1,3}: "bac", "bad", "cad", "cbd".
Therefore, the second smallest in lexicographical order, "bad," is the answer.
Sample Input 2
18 26 10275802967
10
14
9
13
7
8
2
6
11
18
12
1
4
3
16
5
17
15

Output for the Sample Input 2
ritsumeicampdaytwo

data_split: test


name: CODE FESTIVAL 2017 qual A - Modern Painting

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>1600</var> 点

問題文

現代美術に興味を持ったりんごさんは、CODE FESTIVAL 2017 の会場に作られた <var>N+2</var> 行 <var>M+2</var> 列の盤面と、何人かの人を使って絵を描くことにしました。

盤面の上から <var>i+1</var> 行目、左から <var>j+1</var> 列目のマスは <var>2</var> つの整数の組 <var>(i,j)</var> であらわされます。すなわち、左上のマスが <var>(0,0)</var> で、右下のマスが <var>(N+1,M+1)</var> です。
最初、<var>1 \leq x \leq N, 1 \leq y \leq M</var> を満たすマス <var>(x,y)</var> は白で塗られており、それ以外の (外周の) マスは黒で塗られています。

りんごさんは、盤面の外周のマスのうちのいくつかに、人を内向きに配置しました。
より厳密には、配置の情報は <var>4</var> つの文字列 <var>A,B,C,D</var> によってあらわされ、以下のように配置が行われます。

端以外の各行について、<var>A</var> の <var>i(1 \leq i \leq N)</var> 文字目が 1 のときマス <var>(i,0)</var> に、右を向いた人を <var>1</var> 人配置する。そうでないとき、何もしない。

端以外の各行について、<var>B</var> の <var>i(1 \leq i \leq N)</var> 文字目が 1 のときマス <var>(i,M+1)</var> に、左を向いた人を <var>1</var> 人配置する。そうでないとき、何もしない。

端以外の各列について、<var>C</var> の <var>i(1 \leq i \leq M)</var> 文字目が 1 のときマス <var>(0,i)</var> に、下を向いた人を <var>1</var> 人配置する。そうでないとき、何もしない。

端以外の各列について、<var>D</var> の <var>i(1 \leq i \leq M)</var> 文字目が 1 のときマス <var>(N+1,i)</var> に、上を向いた人を <var>1</var> 人配置する。そうでないとき、何もしない。

各人はそれぞれ、白でない色のペンキを充分な量持っています。どの相異なる <var>2</var> 人の持っているペンキの色も、互いに異なります。

人の配置の例(便宜上、黒く塗られたマスを灰色で表しています)

りんごさんは、以下の一連の操作を、全ての人が会場から追い出されていなくなるまで繰り返します。

まだ追い出されていない人を <var>1</var> 人選ぶ。

選ばれた人は、目の前のマスが白で塗られている間、自分の向いている向きに <var>1</var> マス分進み、進んだ先のマスを自分の持っているペンキで塗る。目の前のマスが白で塗られていない場合、動作を終了する。

動作を終了した人を会場から追い出す。

塗られ方の例

りんごさんが作ることのできる、最終的な盤面の塗られ方は何通りあるでしょうか。<var>998244353</var> で割ったあまりを求めてください。

なお、 <var>2</var> つの盤面の塗られ方が異なるとは、あるマスが存在し、そのマスの色が異なることを指します。

制約

<var>1 \leq N,M \leq 10^5</var>

<var>|A|=|B|=N</var>

<var>|C|=|D|=M</var>

<var>A,B,C,D</var> は 0 と 1 からなる

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var> <var>M</var>
<var>A</var>
<var>B</var>
<var>C</var>
<var>D</var>

出力

最終的な盤面の塗られ方の総数を <var>998244353</var> で割ったあまりを出力せよ。

入力例 1

2 2
10
01
10
01

出力例 1

6

以下の <var>6</var> 通りの塗られ方があります。

入力例 2

2 2
11
11
11
11

出力例 2

32

入力例 3

3 4
111
111
1111
1111

出力例 3

1276

入力例 4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

出力例 4

548356548

<var>998244353</var> で割ったあまりを求めるのを忘れないようにしてください。

入力例 5

3 4
000
101
1111
0010

出力例 5

21

入力例 6

9 13
111100001
010101011
0000000000000
1010111111101

出力例 6

177856

入力例 7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

出力例 7

734524988

Score : <var>1600</var> points

Problem Statement

Ringo got interested in modern art. He decided to draw a big picture on the board with <var>N+2</var> rows and <var>M+2</var> columns of squares constructed in the venue of CODE FESTIVAL 2017, using some people.

The square at the <var>(i+1)</var>-th row and <var>(j+1)</var>-th column in the board is represented by the pair of integers <var>(i,j)</var>. That is, the top-left square is <var>(0,0)</var>, and the bottom-right square is <var>(N+1,M+1)</var>.
Initially, the squares <var>(x,y)</var> satisfying <var>1 \leq x \leq N</var> and <var>1 \leq y \leq M</var> are painted white, and the other (outermost) squares are painted black.

Ringo arranged people at some of the outermost squares, facing inward.
More specifically, the arrangement of people is represented by four strings <var>A</var>, <var>B</var>, <var>C</var> and <var>D</var>, as follows:

For each row except the top and bottom, if the <var>i</var>-th character <var>(1 \leq i \leq N)</var> in <var>A</var> is 1, place a person facing right at the square <var>(i,0)</var>; otherwise, do nothing.

For each row except the top and bottom, if the <var>i</var>-th character <var>(1 \leq i \leq N)</var> in <var>B</var> is 1, place a person facing left at the square <var>(i,M+1)</var>; otherwise, do nothing.

For each column except the leftmost and rightmost, if the <var>i</var>-th character <var>(1 \leq i \leq M)</var> in <var>C</var> is 1, place a person facing down at the square <var>(0,i)</var>; otherwise, do nothing.

For each column except the leftmost and rightmost, if the <var>i</var>-th character <var>(1 \leq i \leq M)</var> in <var>D</var> is 1, place a person facing up at the square <var>(N+1,i)</var>; otherwise, do nothing.

Each person has a sufficient amount of non-white paint. No two people have paint of the same color.

An example of an arrangement of people (For convenience, black squares are displayed in gray)

Ringo repeats the following sequence of operations until all people are dismissed from the venue.

Select a person who is still in the venue.

The selected person repeats the following action while the square in front of him/her is white: move one square forward, and paint the square he/she enters with his/her paint. When the square in front of him/her is not white, he/she stops doing the action.

The person is now dismissed from the venue.

An example of a way the board is painted

How many different states of the board can Ringo obtain at the end of the process? Find the count modulo <var>998244353</var>.

Two states of the board are considered different when there is a square painted in different colors.

Constraints

<var>1 \leq N,M \leq 10^5</var>

<var>|A|=|B|=N</var>

<var>|C|=|D|=M</var>

<var>A</var>, <var>B</var>, <var>C</var> and <var>D</var> consist of 0 and 1.

Input

Input is given from Standard Input in the following format:

<var>N</var> <var>M</var>
<var>A</var>
<var>B</var>
<var>C</var>
<var>D</var>

Output

Print the number of the different states of the board Ringo can obtain at the end of the process, modulo <var>998244353</var>.

Sample Input 1

2 2
10
01
10
01

Sample Output 1

6

There are six possible states as shown below.

Sample Input 2

2 2
11
11
11
11

Sample Output 2

32

Sample Input 3

3 4
111
111
1111
1111

Sample Output 3

1276

Sample Input 4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

Sample Output 4

548356548

Be sure to find the count modulo <var>998244353</var>.

Sample Input 5

3 4
000
101
1111
0010

Sample Output 5

21

Sample Input 6

9 13
111100001
010101011
0000000000000
1010111111101

Sample Output 6

177856

Sample Input 7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

Sample Output 7

734524988

question:
Ringo got interested in modern art. He decided to draw a big picture on the board with $N+2$ rows and $M+2$ columns of squares constructed in the venue of CODE FESTIVAL 2017, using some people.
The square at the $(i+1)$-th row and $(j+1)$-th column in the board is represented by the pair of integers $(i,j)$. That is, the top-left square is $(0,0)$, and the bottom-right square is $(N+1,M+1)$.
Initially, the squares $(x,y)$ satisfying $1 \leq x \leq N$ and $1 \leq y \leq M$ are painted white, and the other (outermost) squares are painted black.
Ringo arranged people at some of the outermost squares, facing inward.
More specifically, the arrangement of people is represented by four strings $A$, $B$, $C$ and $D$, as follows:

- For each row except the top and bottom, if the $i$-th character $(1 \leq i \leq N)$ in $A$ is 1, place a person facing right at the square $(i,0)$; otherwise, do nothing.
- For each row except the top and bottom, if the $i$-th character $(1 \leq i \leq N)$ in $B$ is 1, place a person facing left at the square $(i,M+1)$; otherwise, do nothing.
- For each column except the leftmost and rightmost, if the $i$-th character $(1 \leq i \leq M)$ in $C$ is 1, place a person facing down at the square $(0,i)$; otherwise, do nothing.
- For each column except the leftmost and rightmost, if the $i$-th character $(1 \leq i \leq M)$ in $D$ is 1, place a person facing up at the square $(N+1,i)$; otherwise, do nothing.

Each person has a sufficient amount of non-white paint. No two people have paint of the same color.

![image](1.png)
An example of an arrangement of people (For convenience, black squares are displayed in gray)

Ringo repeats the following sequence of operations until all people are dismissed from the venue.

- Select a person who is still in the venue.
- The selected person repeats the following action while the square in front of him/her is white: move one square forward, and paint the square he/she enters with his/her paint. When the square in front of him/her is not white, he/she stops doing the action.
- The person is now dismissed from the venue.

![image](2.png)
An example of a way the board is painted

How many different states of the board can Ringo obtain at the end of the process? Find the count modulo $998244353$.
Two states of the board are considered different when there is a square painted in different colors.

Constraints

- $1 \leq N,M \leq 10^5$
- $|A|=|B|=N$
- $|C|=|D|=M$
- $A$, $B$, $C$ and $D$ consist of 0 and 1.

Input
Input is given from Standard Input in the following format:
$N$ $M$

$A$

$B$

$C$

$D$

Output
Print the number of the different states of the board Ringo can obtain at the end of the process, modulo $998244353$.

Sample Input 1
2 2
10
01
10
01

Sample Output 1
6

There are six possible states as shown below.
![image](3.png)

Sample Input 2
2 2
11
11
11
11

Sample Output 2
32

Sample Input 3
3 4
111
111
1111
1111

Sample Output 3
1276

Sample Input 4
17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

Sample Output 4
548356548

Be sure to find the count modulo $998244353$.

Sample Input 5
3 4
000
101
1111
0010

Sample Output 5
21

Sample Input 6
9 13
111100001
010101011
0000000000000
1010111111101

Sample Output 6
177856

Sample Input 7
23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

Sample Output 7
734524988

image_tags: Map Map Map

data_split: test


solutions: ["import math\n(N, D) = list(map(int, input().split()))\nDs = list(map(int, input().split()))\nQ = int(input())\nQs = list(map(int, input().split()))\ndp = [math.inf] * (N + 1)\ndp[-1] = 1\nfor i in range(N - 1, -1, -1):\n\tif Ds[i] >= 2 * dp[i + 1]:\n\t\tdp[i] = dp[i + 1]\n\telse:\n\t\tdp[i] = dp[i + 1] + Ds[i]\nPos = [D]\nfor i in range(N):\n\tif Ds[i] > Pos[-1] * 2:\n\t\tPos.append(Pos[-1])\n\telse:\n\t\tPos.append(abs(Pos[-1] - Ds[i]))\nfor q in Qs:\n\tif dp[q] > Pos[q - 1]:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')\n", "(n, D) = map(int, input().split())\nx = list(map(int, input().split()))\nQ = int(input())\nq = list(map(int, input().split()))\nind = [D]\nfor i in range(n):\n\tind.append(min(ind[-1], abs(ind[-1] - x[i])))\nl = [1]\nfor i in range(n - 1, -1, -1):\n\tif x[i] < 2 * l[-1]:\n\t\tl.append(x[i] + l[-1])\n\telse:\n\t\tl.append(l[-1])\nl = l[::-1]\nfor i in range(Q):\n\tif l[q[i]] <= ind[q[i] - 1]:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "import sys\nsys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline()[:-1]\n\ndef main():\n\t(dn, s) = MI()\n\tdd = LI()\n\tqn = II()\n\tqq = LI()\n\tqi = [(q - 1, i) for (i, q) in enumerate(qq)]\n\tpos = [s]\n\tfor d in dd:\n\t\tpos.append(min(pos[-1], abs(d - pos[-1])))\n\tbb = [1] * (dn + 1)\n\tfor i in range(dn - 1, -1, -1):\n\t\td = dd[i]\n\t\tif d < bb[i + 1] * 2:\n\t\t\tbb[i] = bb[i + 1] + d\n\t\telse:\n\t\t\tbb[i] = bb[i + 1]\n\tans = [''] * qn\n\tfor (q, ai) in qi:\n\t\tif pos[q] >= bb[q + 1]:\n\t\t\tans[ai] = 'YES'\n\t\telse:\n\t\t\tans[ai] = 'NO'\n\tprint(*ans, sep='\\n')\nmain()\n", "(N, start) = map(int, input().split())\nD = list(map(int, input().split()))\ninput()\nQ = list(map(int, input().split()))\nQ = [(k - 1, i) for (i, k) in enumerate(Q)]\nQ.sort()\nP = [start]\nfor d in D:\n\ta = P[-1]\n\tb = abs(a - d)\n\tP.append(min(a, b))\nresult = [None] * len(Q)\nx = 1\nfor (i, d) in zip(reversed(range(len(D))), reversed(D)):\n\tif Q[-1][0] == i:\n\t\tresult[Q[-1][1]] = P[i] >= x\n\t\tQ.pop()\n\t\tif not Q:\n\t\t\tbreak\n\tif abs(x - d) < x:\n\t\tx += d\nfor r in result:\n\tprint('YES' if r else 'NO')\n", "(N, D) = list(map(int, input().split()))\nd = list(map(int, input().split()))\nQ = int(input())\nq = list(map(int, input().split()))\ndis = [0 for i in range(N + 1)]\ndis[0] = D\nfor i in range(N):\n\tdis[i + 1] = min(dis[i], abs(dis[i] - d[i]))\ndp = [0 for i in range(N + 1)]\ndp[N] = 1\nfor i in range(N - 1, -1, -1):\n\tif dp[i + 1] <= d[i] // 2:\n\t\tdp[i] = dp[i + 1]\n\telse:\n\t\tdp[i] = dp[i + 1] + d[i]\nfor qi in range(Q):\n\tprint(['NO', 'YES'][dis[q[qi] - 1] >= dp[q[qi]]])\n", "(n, d) = list(map(int, input().split()))\nD = list(map(int, input().split()))\nA = [0] * (n + 1)\nP = [0] * (n + 1)\nP[0] = pos = d\nfor (i, x) in enumerate(D):\n\tif x <= 2 * pos:\n\t\tpos = abs(x - pos)\n\tP[i + 1] = pos\n\tif pos == 0:\n\t\tbreak\nfor i in range(n - 1, -1, -1):\n\tif D[i] <= 2 * A[i + 1] + 1:\n\t\tA[i] = A[i + 1] + D[i]\n\telse:\n\t\tA[i] = A[i + 1]\nq = input()\nQ = list(map(int, input().split()))\nfor i in Q:\n\tif P[i - 1] <= A[i] and pos == 0:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')\n", "import sys\ninput = sys.stdin.readline\n(N, dist) = map(int, input().split())\nD = [int(x) for x in input().split()]\nstart_dist = [dist]\nfor d in D:\n\tx = start_dist[-1]\n\ty = min(abs(x - d), x)\n\tstart_dist.append(y)\nng_dist = [None] * (N + 1)\nng_dist[N] = 1\nfor (i, d) in enumerate(D[::-1]):\n\tx = ng_dist[N - i]\n\ty = x if x <= d // 2 else x + d\n\tng_dist[N - i - 1] = y\ninput()\nQ = [int(x) for x in input().split()]\nanswer = ['YES' if ng_dist[d] <= start_dist[d - 1] else 'NO' for d in Q]\nprint('\\n'.join(answer))\n", "def solve(n, d, da, q, qa):\n\ta = [d]\n\tx = d\n\tfor di in da:\n\t\tx = min(x, max(x - di, di - x))\n\t\ta.append(x)\n\tb = [1]\n\tx = 1\n\tfor i in range(n - 1, -1, -1):\n\t\tdi = da[i]\n\t\tif di // 2 < x:\n\t\t\tx += di\n\t\tb.append(x)\n\tb.reverse()\n\tfor qi in qa:\n\t\tif b[qi] <= a[qi - 1]:\n\t\t\tprint('YES')\n\t\telse:\n\t\t\tprint('NO')\n\ndef main():\n\t(n, d) = input().split()\n\tn = int(n)\n\td = int(d)\n\tda = list(map(int, input().split()))\n\tq = input()\n\tq = int(q)\n\tqa = list(map(int, input().split()))\n\tsolve(n, d, da, q, qa)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "import sys\nreadline = sys.stdin.readline\n(N, D) = list(map(int, readline().split()))\nA = list(map(int, readline().split())) + [0]\nreach = [None] * (N + 2)\nreach[-1] = D\nfor i in range(N + 1):\n\tr = reach[i - 1]\n\ta = A[i]\n\treach[i] = min(r, abs(r - a))\nputter = [0] * (N + 2)\nfor i in range(N, -1, -1):\n\tp = putter[i + 1]\n\ta = A[i]\n\tif 2 * p + 1 >= a:\n\t\tp += a\n\tputter[i] = p\nres = ['NO'] * N\nfor i in range(N):\n\tif reach[i - 1] > putter[i + 1]:\n\t\tres[i] = 'YES'\nQ = int(readline())\nprint('\\n'.join((res[int(i) - 1] for i in readline().split())))\n", "import sys\nimport math\n(N, D) = list(map(int, sys.stdin.readline().rstrip().split()))\nds = list(map(int, sys.stdin.readline().rstrip().split()))\n(Q,) = list(map(int, sys.stdin.readline().rstrip().split()))\nqs = list(map(int, sys.stdin.readline().rstrip().split()))\ntargets = [1]\nfor d in reversed(ds):\n\tif d // 2 < targets[-1]:\n\t\ttargets.append(targets[-1] + d)\n\telse:\n\t\ttargets.append(targets[-1])\ntargets.reverse()\ncurrent = D\ncan_avoids = []\nfor i in range(N):\n\td = ds[i]\n\ttarget = targets[i + 1]\n\tcan_avoids.append(current >= target)\n\tif d // 2 < current:\n\t\tcurrent -= d\n\t\tcurrent = max(-current, current)\nfor q in qs:\n\tif can_avoids[q - 1]:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\nreturn\n", "(N, D) = map(int, input().split())\nds = list(map(int, input().split()))\nQ = int(input())\nquerys = list(map(lambda x: int(x) - 1, input().split()))\nps = [0] * (N + 1)\nps[0] = D\nfor i in range(N):\n\tps[i + 1] = min(abs(ps[i] - ds[i]), ps[i])\nif ps[N] != 0:\n\tprint('\\n'.join(['YES'] * Q))\n\texit()\nms = [0] * (N + 1)\nfor i in range(N)[::-1]:\n\tif ms[i + 1] + 1 >= ds[i] - ms[i + 1]:\n\t\tms[i] = ms[i + 1] + ds[i]\n\telse:\n\t\tms[i] = ms[i + 1]\nfor q in querys:\n\tif ps[q] <= ms[q + 1]:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')\n", "(N, D) = map(int, input().split())\ndv = list(map(int, input().split()))\nQ = int(input())\nqv = list(map(int, input().split()))\ndist_alice = D\ndist_alice_list = [D]\nfor i in range(N):\n\tif dist_alice >= dv[i]:\n\t\tdist_alice -= dv[i]\n\telif 2 * dist_alice >= dv[i]:\n\t\tdist_alice = dv[i] - dist_alice\n\tdist_alice_list.append(dist_alice)\nsol_min = [1]\nsol_min_ = 1\nfor i in range(N - 1, -1, -1):\n\tif 2 * sol_min_ > dv[i]:\n\t\tsol_min_ += dv[i]\n\tsol_min.append(sol_min_)\nfor i in range(Q):\n\tif dist_alice_list[qv[i] - 1] >= sol_min[N - qv[i]]:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nreadlines = sys.stdin.buffer.readlines\n(N, X) = map(int, readline().split())\nD = [0] + list(map(int, readline().split()))\nreadline()\nQ = list(map(int, read().split()))\nstart = [X] * (N + 2)\nfor (n, d) in enumerate(D[1:], 1):\n\tx = start[n]\n\ty = min(x, abs(x - d))\n\tstart[n + 1] = y\nmin_ng = [1] * (N + 2)\nfor n in range(N, 0, -1):\n\td = D[n]\n\tx = min_ng[n + 1]\n\ty = x + d\n\tif x + x <= d:\n\t\ty = x\n\tmin_ng[n] = y\nanswer = ['YES' if x >= y else 'NO' for (x, y) in zip(start, min_ng[1:])]\nprint('\\n'.join((answer[q] for q in Q)))\n", "(N, D) = list(map(int, input().split()))\nd = list(map(int, input().split()))\nQ = int(input())\nq = list(map(int, input().split()))\na = [D for i in range(N)]\nb = [1 for i in range(N + 1)]\nfor i in range(1, N):\n\ta[i] = min(abs(a[i - 1] - d[i - 1]), a[i - 1])\nfor i in range(N)[::-1]:\n\tif d[i] // 2 < b[i + 1]:\n\t\tb[i] = b[i + 1] + d[i]\n\telse:\n\t\tb[i] = b[i + 1]\nres = ''\nfor i in q:\n\tif a[i - 1] < b[i]:\n\t\tres += 'NO'\n\telse:\n\t\tres += 'YES'\n\tres += '\\n'\nprint(res)\n"]

name: AtCoder Regular Contest 072 - Alice in linear land

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>900</var> 点

問題文

Aliceは数直線の上に住んでいます。今日はある不思議な乗り物に乗って目的地まで行くことを考えました。
はじめ、Aliceは目的地から <var>D</var> 離れたところにいます。Aliceが乗り物にある数 <var>x</var> を入力すると、現在地から目的地に向かって <var>x</var> 進んだところが現在地より目的地に近いとき移動し、そうでないときは動きません。現在地から目的地までの距離が <var>x</var> 未満のとき、<var>x</var> 進んだところは目的地を通りすぎていることに注意してください。また、目的地を通り過ぎると進行方向が変わること、進行方向は何度も変わることがあることに注意してください。

Aliceは乗り物に <var>N</var> 回だけ数を入力し、<var>i</var> 番目に入力する数は <var>d_i</var> の予定でした。Aliceは入力する予定数の書かれたリストを作っておき、その数を <var>1</var> つずつ入力します。

しかしイタズラ好きの魔法使いが現れ、Aliceが <var>N</var> 回の入力による移動を終えても目的地にたどり着かないよう、リストの数を <var>1</var> つだけ書き換えることを考えました。

魔法使いはイタズラの実行のため以下の <var>Q</var> 個の計画を考えています。

<var>q_i</var> 回目に入力する数のみをある正整数に変更することで、Aliceが目的地にたどり着かないようにする

<var>Q</var> 個の計画それぞれが実行可能であるか答えるプログラムを書いてください。

制約

<var>1≦ N ≦ 5*10^5</var>

<var>1≦ Q ≦ 5*10^5</var>

<var>1≦ D ≦ 10^9</var>

<var>1≦ d_i ≦ 10^9(1≦i≦N)</var>

<var>1≦ q_i ≦ N(1≦i≦Q)</var>

<var>d_i, D</var>は整数である

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var> <var>D</var>
<var>d_1</var> <var>d_2</var> <var>...</var> <var>d_N</var>
<var>Q</var>
<var>q_1</var> <var>q_2</var> <var>...</var> <var>q_Q</var>

出力

<var>i</var> 番目の計画が実行可能ならYES、そうでないならNOと <var>i</var> 行目に出力せよ。

入力例 1

4 10
3 4 3 3
2
4 3

出力例 1

NO
YES

<var>3</var> 番目までの入力でAliceはすでに目的地にたどり着いているため、<var>1</var> 番目の計画の答えはNOです。

例えば、<var>3</var> 番目の入力を <var>5</var> にすると、Aliceは以下のような移動をし、目的地にたどり着くことはできないため、<var>2</var> 番目の計画の答えはYESです。

入力例 2

5 9
4 4 2 3 2
5
1 4 2 3 5

出力例 2

YES
YES
YES
YES
YES

もともと入力する予定のままでもAliceは目的地にたどり着けないため、すべての計画は実行可能です。

入力例 3

6 15
4 3 5 4 2 1
6
1 2 3 4 5 6

出力例 3

NO
NO
YES
NO
NO
YES

Score : <var>900</var> points

Problem Statement

Alice lives on a line. Today, she will travel to some place in a mysterious vehicle.
Initially, the distance between Alice and her destination is <var>D</var>. When she input a number <var>x</var> to the vehicle, it will travel in the direction of the destination by a distance of <var>x</var> if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than <var>x</var>.

Alice made a list of <var>N</var> numbers. The <var>i</var>-th number in this list is <var>d_i</var>. She will insert these numbers to the vehicle one by one.

However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after <var>N</var> moves.

She has <var>Q</var> plans to do this, as follows:

Rewrite only the <var>q_i</var>-th number in the list with some integer so that Alice will not reach the destination.

Write a program to determine whether each plan is feasible.

Constraints

<var>1≤ N ≤ 5*10^5</var>

<var>1≤ Q ≤ 5*10^5</var>

<var>1≤ D ≤ 10^9</var>

<var>1≤ d_i ≤ 10^9(1≤i≤N)</var>

<var>1≤ q_i ≤ N(1≤i≤Q)</var>

D and each <var>d_i</var> are integers.

Input

Input is given from Standard Input in the following format:

<var>N</var> <var>D</var>
<var>d_1</var> <var>d_2</var> <var>...</var> <var>d_N</var>
<var>Q</var>
<var>q_1</var> <var>q_2</var> <var>...</var> <var>q_Q</var>

Output

Print <var>Q</var> lines. The <var>i</var>-th line should contain YES if the <var>i</var>-th plan is feasible, and NO otherwise.

Sample Input 1

4 10
3 4 3 3
2
4 3

Sample Output 1

NO
YES

For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO.
For the second plan, rewriting the third number in the list with <var>5</var> will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES.

Sample Input 2

5 9
4 4 2 3 2
5
1 4 2 3 5

Sample Output 2

YES
YES
YES
YES
YES

Alice will not reach the destination as it is, and therefore all the plans are feasible.

Sample Input 3

6 15
4 3 5 4 2 1
6
1 2 3 4 5 6

Sample Output 3

NO
NO
YES
NO
NO
YES

question:
Alice lives on a line. Today, she will travel to some place in a mysterious vehicle.
Initially, the distance between Alice and her destination is $D$. When she input a number $x$ to the vehicle, it will travel in the direction of the destination by a distance of $x$ if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than $x$.
Alice made a list of $N$ numbers. The $i$-th number in this list is $d_i$. She will insert these numbers to the vehicle one by one.
However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after $N$ moves.
She has $Q$ plans to do this, as follows:

- Rewrite only the $q_i$-th number in the list with some integer so that Alice will not reach the destination.

Write a program to determine whether each plan is feasible.

Constraints

- $1≤ N ≤ 5*10^5$
- $1≤ Q ≤ 5*10^5$
- $1≤ D ≤ 10^9$
- $1≤ d_i ≤ 10^9(1≤i≤N)$
- $1≤ q_i ≤ N(1≤i≤Q)$
- D and each $d_i$ are integers.

Input
Input is given from Standard Input in the following format:
$N$ $D$

$d_1$ $d_2$ $...$ $d_N$

$Q$

$q_1$ $q_2$ $...$ $q_Q$

Output
Print $Q$ lines. The $i$-th line should contain YES if the $i$-th plan is feasible, and NO otherwise.

Sample Input 1
4 10
3 4 3 3
2
4 3

Sample Output 1
NO
YES

For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO.
For the second plan, rewriting the third number in the list with $5$ will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES.
![image](1.png)

Sample Input 2
5 9
4 4 2 3 2
5
1 4 2 3 5

Sample Output 2
YES
YES
YES
YES
YES

Alice will not reach the destination as it is, and therefore all the plans are feasible.

Sample Input 3
6 15
4 3 5 4 2 1
6
1 2 3 4 5 6

Sample Output 3
NO
NO
YES
NO
NO
YES

data_split: test


Identically Colored Panels Connection

source: ACM International Collegiate Programming Contest, Japan Domestic 2011

raw_problem:
Identically Colored Panels Connection

Dr. Fukuoka has invented fancy panels.

Each panel has a square shape of a unit size and
has one of the six colors, namely, yellow, pink, red, purple, green and blue.

The panel has two remarkable properties.

One property is that, when two or more panels with the same color
are placed adjacently, their touching edges melt a little
and they are fused each other.
The fused panels are united into a polygonally shaped panel.

The other property is that the color of a panel can be changed
to one of six colors by giving an electrical shock.
The resulting color can be controlled by its waveform.
The electrical shock to an already united panel changes
the color of the whole to a specified single color.

Since he wants to investigate the strength with respect to the
color and the size of a united panel compared to unit panels,
he tries to unite panels into a polygonal panel with a specified color.

Figure C-1: panels and their initial colors

Since many panels are simultaneously synthesized and generated on a base plate
through some complex chemical processes,
the fabricated panels are randomly colored and
they are arranged in a rectangular shape on the base plate  (Figure C-1).

Note that the two purple (color 4) panels in Figure C-1 are
already united at the initial state since they are
adjacent to each other.

Installing  electrodes to a panel, and
changing its color several times by giving electrical shocks
according to an appropriate sequence for a specified target color,
he can make a united panel merge the adjacent panels
to unite them step by step
and can obtain a larger panel with the target color.

Unfortunately, panels will be broken when
they are struck by the sixth electrical shock.

That is, he can change the color of a panel or a united panel only
five times.

Let us consider a case
where the panel at the upper left corner of the panel configuration
(Figure C-1) is attached with the electrodes.
First, changing the color of the panel from yellow to blue,
the two adjacent panels are fused into a united panel (Figure C-2).

Figure C-2:
Change of the color of the panel at the upper left corner,
from yellow (color 1) to blue (color 6).

Second, changing the color of the upper left united panel from blue
to red, a united red panel that consists of three unit panels is newly formed
(Figure C-3).
Then, changing the color of the united panel from red to purple,
panels are united again to form a united panel of five unit panels
(Figure C-4).

Figure C-3:
Change of the color of the panel at the upper left corner,
from blue (color 6) to red (color 3).

Figure C-4:
Change of the color of the panel at the upper left corner,
from red (color 3) to purple (color 4).

Furthermore, through making a pink united panel in Figure C-5 by
changing the color from purple to pink,
then, the green united panel in Figure C-6 is obtained
by changing the color from pink to green.
The green united panel consists of ten unit panels.

Figure C-5:
Change of the color of the panel at the upper left corner,
from  purple (color 4) to pink (color 2).

Figure C-6:
Change of the color of the panel at the upper left corner,
from pink (color 2) to green (color 5).

In order to check the strength of united panels with
various sizes and colors, he needs to unite as many panels
as possible with the target color.

Your job is to write a program that finds a sequence to change
the colors five times
in order to get the largest united panel with the target color.

Note that the electrodes are fixed to the panel at the upper left corner.

Input

The input consists of multiple datasets, each being in the following format.

h w c

p1,1 p1,2 ... p1,w

p2,1 p2,2 ... p2,w

...

ph,1 ph,2 ... ph,w

h and w are positive integers no more than 8 that
represent the height and the width of the given rectangle.
c is a positive integer no more than 6 that represents
the target color of the finally united panel.

pi,j is a positive integer no more than 6
that represents the initial color of the panel at the position
(i, j).

The end of the input is indicated by a line that consists of
three zeros separated by single spaces.

Output

For each dataset, output the largest possible number of unit panels
in the united panel at the upper left corner with the target color
after five times of color changes of the panel
at the upper left corner.
No extra characters should occur in the output.

Sample Input

3 5 5
1 6 3 2 5
2 5 4 6 1
1 2 4 1 5
4 5 6
1 5 6 1 2
1 4 6 3 2
1 5 2 3 2
1 1 2 3 2
1 1 5
1
1 8 6
1 2 3 4 5 1 2 3
8 1 1
1
2
3
4
5
1
2
3
8 8 6
5 2 5 2 6 5 4 2
4 2 2 2 5 2 2 2
4 4 4 2 5 2 2 2
6 4 5 2 2 2 6 6
6 6 5 5 2 2 6 6
6 2 5 4 2 2 6 6
2 4 4 4 6 2 2 6
2 2 2 5 5 2 2 2
8 8 2
3 3 5 4 1 6 2 3
2 3 6 4 3 6 2 2
4 1 6 6 6 4 4 4
2 5 3 6 3 6 3 5
3 1 3 4 1 5 6 3
1 6 6 3 5 1 5 3
2 4 2 2 2 6 5 3
4 1 3 6 1 5 5 4
0 0 0

Output for the Sample Input

10
18
1
5
6
64
33

solutions: ["from itertools import product\nfrom heapq import heappush, heappop\nimport sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\ndef solve():\n    H, W, C = map(int, readline().split())\n    if H == W == C == 0:\n        return False\n    P = [list(map(int, readline().split())) for i in range(H)]\n    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))\n    INF = 10\n    ans = 0\n    for p0 in product(range(1, 7), repeat=4):\n        p = p0 + (C,)\n        que = [(0, 0, 0)]\n        dist = [[INF]*W for i in range(H)]\n        dist[0][0] = 0\n        while que:\n            cost, x, y = heappop(que)\n            if dist[y][x] < cost:\n                continue\n            for dx, dy in dd:\n                nx = x + dx; ny = y + dy\n                if not 0 <= nx < W or not 0 <= ny < H:\n                    continue\n                if cost == 0 and P[y][x] == P[ny][nx] and 0 < dist[ny][nx]:\n                    dist[ny][nx] = 0\n                    heappush(que, (0, nx, ny))\n                else:\n                    for k in range(max(cost-1, 0), 5):\n                        if p[k] == P[ny][nx]:\n                            if k+1 < dist[ny][nx]:\n                                dist[ny][nx] = k+1\n                                heappush(que, (k+1, nx, ny))\n                            break\n        r = 0\n        for i in range(H):\n            for j in range(W):\n                if dist[i][j] < INF:\n                    r += 1\n        ans = max(ans, r)\n    write(\"%d\\n\" % ans)\n    return True\nwhile solve():\n    ...\n", "direct = ((0, -1), (0, 1), (-1, 0), (1, 0))\n\ndef comb(target_color, mp, pos):\n  next_pos = pos[:]\n  end = len(next_pos)\n  ind = 0\n  while ind < end:\n    x, y = next_pos[ind]\n    for dx, dy in direct:\n      nx, ny = x + dx, y + dy\n      if mp[ny][nx] == target_color and (nx, ny) not in next_pos:\n        next_pos.append((nx, ny))\n        end += 1\n    ind += 1\n  return next_pos\n\ndef search(rest, now_color, goal_color, pos, mp):\n  if rest == 1:\n    if now_color != goal_color:\n      next_pos = comb(goal_color, mp, pos)\n      return len(next_pos)\n    return 0\n\n  ret = 0\n  for next_color in range(1, 7):\n    if next_color != now_color:\n      next_pos = comb(next_color, mp, pos)\n      ret = max(ret, search(rest - 1, next_color, goal_color, next_pos, mp))\n  return ret\n\ndef main():\n  while True:\n    h, w, c = map(int, input().split())\n    if h == 0:\n      break\n    mp = [[-1] + list(map(int, input().split())) + [-1] for _ in range(h)]\n    mp.insert(0, [-1] * (w + 2))\n    mp.append([-1] * (w + 2))\n    init_pos = [(1, 1)]\n    init_color = mp[1][1]\n    init_pos = comb(init_color, mp, init_pos)\n    print(search(5, init_color, c, init_pos, mp))\nmain()\n", "# case1 2.217sec(PyPy3)\nans1=[12, 15, 10, 8, 13, 8, 13, 6, 9, 10, 13, 12, 12, 18, 11, 1, 2, 8, 12, 3, 15, 3, 9, 8, 6, 10, 8, 5, 19, 14, 8, 5, 13, 8, 17, 15, 19, 14, 20, 9, 6, 9, 7, 12, 3, 5, 8, 11, 19, 9, 3, 16, 21, 16, 15, 5, 13, 1, 10, 16, 13, 6, 4, 18, 17, 8, 12, 6, 19, 5, 17, 6, 9, 12, 8, 5, 29, 15, 2, 6, 18, 1, 13, 8, 7, 8, 9, 8, 13, 9, 16, 8, 4, 14, 1, 17, 11, 13, 14, 8, 14, 8, 14, 8, 15, 10, 13, 9, 7, 10, 10, 8, 8, 16, 20, 6, 21, 8, 12, 3, 5, 6, 19, 8, 9, 16, 13, 11, 8, 12, 3, 2, 22, 8, 19, 8, 15, 10, 6, 8, 1, 18, 8, 12, 9, 12, 14, 9, 12, 12, 4, 18, 12, 2, 9, 6, 17, 6, 9, 16, 8, 18, 6, 14, 17, 14, 12, 1, 14, 6, 14, 8, 4, 19, 20, 11, 10, 8, 8, 9, 9, 9, 17, 16, 8, 9, 14, 6, 9, 4, 9, 8, 9, 8, 12, 8, 12, 10, 18, 15, 13, 4, 17, 9, 9, 9, 2, 9, 5, 6, 9, 4, 9, 8, 27, 8, 4, 8, 8, 8, 11, 12, 6, 14, 6, 16, 9, 9, 17, 11, 13, 17, 17, 13, 8, 17, 5, 21, 5, 6, 16, 10, 8, 5, 3, 2, 9, 16, 20, 14, 4, 8, 14, 9, 10, 9, 12, 15, 8, 8, 9, 8, 9, 15, 5, 5, 9, 7, 18, 5, 5, 4, 3, 17, 4, 8, 20, 5, 5, 5, 15, 17, 8, 12, 21, 18, 9, 14, 8, 8, 10, 12, 9, 10, 9, 5, 14, 5, 4, 3, 20, 11, 12, 18, 9, 10, 13, 5, 8, 4, 6, 64, 10, 13, 17, 6, 14, 16, 5, 9, 8, 16, 9, 14, 17, 13, 23, 17, 9, 14, 10, 8, 14, 13, 9, 33, 17, 13, 8, 9, 9, 9, 16, 17, 11, 9, 15, 16, 11, 10, 17, 2, 8, 14, 22, 23, 8, 2, 14, 15, 6, 6, 9, 8, 19, 20, 4, 16, 9, 2, 9, 9, 6, 17, 15, 14, 11, 8, 9, 8, 20, 9, 16, 13, 2, 12, 7, 14, 8, 14, 10, 6, 8, 9, 12, 9, 8, 22, 16, 22, 9, 3, 8, 15, 8, 8, 17, 3, 13, 19, 30, 15, 19, 6, 14, 14, 8, 18, 9, 8, 14, 9, 6, 9, 8, 3, 13, 12, 16, 4, 5, 6, 2, 10, 2, 9, 12, 24, 1, 20, 8, 8, 5, 9, 19, 20, 5, 19, 8, 8, 9, 5, 8, 16, 13, 8, 4, 5, 9, 5, 4, 9, 11, 8, 4, 6, 8, 8, 15, 9, 35, 8, 5, 20, 16, 9, 13, 5, 12, 10, 8, 9, 23, 9, 5, 16, 23]\n\n# case2 2.611sec(PyPy3)\nans2=[8, 14, 23, 4, 4, 9, 18, 7, 4, 21, 25, 15, 9, 19, 6, 9, 6, 8, 13, 3, 8, 10, 8, 11, 11, 14, 3, 18, 20, 8, 9, 14, 9, 11, 7, 15, 8, 14, 8, 21, 15, 9, 6, 16, 15, 20, 5, 6, 8, 11, 9, 26, 16, 22, 7, 8, 2, 22, 13, 18, 26, 8, 25, 15, 18, 9, 14, 17, 23, 12, 9, 6, 9, 10, 6, 8, 3, 9, 15, 8, 16, 4, 10, 7, 11, 26, 22, 9, 11, 22, 12, 9, 2, 6, 6, 6, 6, 12, 8, 12, 4, 23, 28, 18, 14, 3, 9, 20, 9, 9, 8, 9, 10, 6, 13, 10, 10, 9, 2, 4, 6, 13, 23, 19, 21, 4, 30, 27, 23, 11, 16, 6, 8, 25, 6, 8, 18, 8, 20, 8, 5, 4, 1, 7, 13, 8, 9, 6, 8, 22, 4, 24, 9, 33, 19, 14, 27, 5, 4, 17, 11, 9, 9, 22, 9, 15, 9, 2, 10, 8, 8, 6, 9, 16, 11, 5, 64, 17, 20, 9, 8, 8, 17, 6, 19, 2, 16, 20, 13, 15, 8, 15, 26, 24, 1, 22, 28, 9, 4, 13, 9, 6, 15, 5, 8, 3, 1, 3, 12, 22, 16, 14, 8, 18, 16, 8, 22, 4, 4, 5, 9, 8, 4, 19, 22, 28, 21, 7, 16, 16, 8, 14, 9, 20, 18, 9, 8, 19, 8, 15, 14, 28, 13, 9, 11, 8, 9, 12, 7, 4, 9, 10, 8, 19, 11, 21, 16, 29, 14, 5, 20, 13, 5, 17, 17, 18, 8, 9, 8, 15, 21, 17, 3, 33, 8, 8, 10, 15, 26, 11, 16, 20, 5, 8, 18, 3, 12, 17, 15, 9, 1, 14, 1, 21, 2, 8, 29, 21, 14, 8, 6, 17, 8, 6, 9, 5, 9, 8, 6, 12, 11, 7, 8, 5, 3, 16, 9, 10, 14, 5, 5, 3, 17, 8, 9, 15, 13, 10, 4, 2, 22, 10, 2, 6, 9, 8, 12, 8, 17, 7, 21, 8, 9, 9, 9, 16, 9, 9, 14, 8, 5, 15, 8, 17, 22, 16, 3, 11, 11, 5, 10, 2, 11, 19, 19, 8, 12, 9, 16, 13, 5, 10, 13, 13, 9, 28, 9, 17, 5, 5, 6, 15, 13, 8, 20, 10, 19, 17, 21, 9, 8, 9, 14, 11, 2, 9, 11, 9, 9, 9, 25, 9, 13, 20, 1, 9, 12, 23, 25, 16, 8, 9, 9, 9, 12, 12, 8, 6, 16, 15, 4, 16, 11, 17, 6, 10, 18, 10, 7, 9, 23, 9, 16, 10, 13, 16, 10, 5, 12, 8, 2, 12, 10, 17, 15, 17, 13, 26, 27, 15, 10, 8, 8, 6, 12, 8, 20, 8, 12, 9, 7, 19, 3, 4, 1, 19, 13, 2, 14, 10, 16, 25, 8, 12, 14, 8, 7, 12, 10, 15, 8, 15, 7, 6, 7, 5, 5]\n\nh,w,c=map(int,input().split())\nif w==2:\n  for i in ans1:\n    print(i)\nelse:\n  for i in ans2:\n    print(i)\n'''\nimport sys\nimport os\nf = open('input.txt', 'r', encoding=\"utf-8_sig\")\nsys.stdin = f\n\nfrom time import time\nstart=time()\n\n\ndxdy=[(1,0),(0,1),(-1,0),(0,-1)]\n\ndef dfs(k):\n  same=[]\n  c0=a[0][0]\n  todo=[(0,0)]\n  seen[0][0]=True\n  while todo:\n    x,y=todo.pop()\n    same.append((x,y))\n    for dx,dy in dxdy:\n      nx,ny=x+dx,y+dy\n      if 0<=nx<h and 0<=ny<w and not seen[nx][ny] and a[nx][ny]==c0:\n        seen[nx][ny]=True\n        todo.append((nx,ny))\n  for x,y in same:\n    seen[x][y]=False\n  \n  if k==5:\n    if c0==c:\n      return len(same)\n    else:\n      return 0\n  ans=0\n\n  for i in range(1,7):\n    for x,y in same:\n      a[x][y]=i\n    ans=max(ans,dfs(k+1))\n  for x,y in same:\n    a[x][y]=c0\n  \n  return ans\n\nANS=[]\nwhile True:\n  h,w,c=map(int,input().split())\n  if h==w==c==0:\n    print(time()-start)\n    print(ANS)\n    exit()\n  a=[list(map(int,input().split())) for i in range(h)]\n  seen=[[False]*w for i in range(h)]\n  ans=dfs(0)\n  ANS.append(ans)\n'''\n", "#!usr/bin/env python3\nfrom collections import defaultdict,deque\nfrom heapq import heappush, heappop\nimport sys\nimport math\nimport bisect\nimport random\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef I(): return int(sys.stdin.readline())\ndef LS():return [list(x) for x in sys.stdin.readline().split()]\ndef S(): return list(sys.stdin.readline())[:-1]\ndef IR(n):\n    return [I() for i in range(n)]\ndef LIR(n):\n    return [LI() for i in range(n)]\ndef SR(n):\n    return [S() for i in range(n)]\ndef LSR(n):\n    return [LS() for i in range(n)]\n\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\n#2005_c\n\"\"\"\nn = int(input())\nk = list(\"mcxi\")\nfor i in range(n):\n    d = {\"m\":0,\"c\":0,\"x\":0,\"i\":0}\n    a,b  = input().split()\n    a = list(a)\n    b = list(b)\n    a.insert(0,1)\n    b.insert(0,1)\n    for j in range(1,len(a)):\n        if a[j] in k:\n            if a[j-1] in k:\n                d[a[j]] += 1\n            else:\n                d[a[j]] += int(a[j-1])\n    for j in range(1,len(b))[::-1]:\n        if b[j] in k:\n            if b[j-1] in k:\n                d[b[j]] += 1\n            else:\n                d[b[j]] += int(b[j-1])\n            if d[b[j]] >= 10:\n                l = b[j]\n                while d[l] >= 10:\n                    d[l] -= 10\n                    l = k[k.index(l)-1]\n                    d[l] += 1\n    for j in k:\n        if d[j]:\n            if d[j] == 1:\n                print(j,end = \"\")\n            else:\n                print(str(d[j])+j,end = \"\")\n    print()\n\"\"\"\n\n#2017_c\n\"\"\"\nwhile 1:\n    h, w = map(int, input().split())\n    if h == w == 0:\n        break\n    s = [list(map(int, input().split())) for i in range(h)]\n\n    ans = 0\n    for u in range(h):\n        for d in range(u+2,h):\n            for l in range(w):\n                for r in range(l+2,w):\n                    m = float(\"inf\")\n                    for i in range(u,d+1):\n                        m = min(m,s[i][l],s[i][r])\n                    for i in range(l,r+1):\n                        m = min(m,s[u][i],s[d][i])\n                    f = 1\n                    su = 0\n                    for i in range(u+1,d):\n                        for j in range(l+1,r):\n                            su += (m-s[i][j])\n                            if s[i][j] >= m:\n                                f = 0\n                                break\n                        if not f:\n                            break\n                    if f:\n                        ans = max(ans,su)\n    print(ans)\n\"\"\"\n\n#2016_c\n\"\"\"\nwhile 1:\n    m,n = map(int, input().split())\n    if m == n == 0:\n        break\n    ma = 7368791\n    d = [0]*(ma+1)\n    z = m\n    for i in range(n):\n        while d[z]:\n            z += 1\n        j = z\n        while j <= ma:\n            d[j] = 1\n            j += z\n    for j in range(z,ma+1):\n        if not d[j]:\n            print(j)\n            break\n\"\"\"\n\n#2018_c\n\"\"\"\ndef factorize(n):\n    if n < 4:\n        return [1,n]\n    i = 2\n    l = [1]\n    while i**2 <= n:\n        if n%i == 0:\n            l.append(i)\n            if n//i != i:\n                l.append(n//i)\n        i += 1\n    l.append(n)\n    l.sort()\n    return l\nwhile 1:\n    b = int(input())\n    if b == 0:\n        break\n    f = factorize(2*b)\n    for n in f[::-1]:\n        a = 1-n+(2*b)//n\n        if a >= 1 and a%2 == 0:\n            print(a//2,n)\n            break\n\"\"\"\n\n#2010_c\n\"\"\"\nimport sys\ndp = [100]*1000000\ndp_2 = [100]*1000000\ndp[0] = 0\ndp_2[0] = 0\nfor i in range(1,181):\n    s = i*(i+1)*(i+2)//6\n    for j in range(s,1000000):\n        if dp[j-s]+1 < dp[j]:\n            dp[j] = dp[j-s]+1\n    if s%2:\n        for j in range(s,1000000):\n            if dp_2[j-s]+1 < dp_2[j]:\n                dp_2[j] = dp_2[j-s]+1\nwhile 1:\n    m = int(sys.stdin.readline())\n    if m == 0:\n        break\n    print(dp[m],dp_2[m])\n\"\"\"\n\n#2015_c\n\"\"\"\nfrom collections import deque\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    s = [input() for i in range(n)]\n    d = [s[i].count(\".\") for i in range(n)]\n    m = max(d)\n    c = [s[i][-1] for i in range(n)]\n    q = deque()\n    for i in range(1,m+1)[::-1]:\n        j = 0\n        while j < n:\n            for k in range(j,n):\n                if d[k] == i:break\n            else:\n                break\n            j = k\n            op = c[j-1]\n            while j < n and d[j] == i:\n                q.append(j)\n                j += 1\n            j = k\n            if op == \"+\":\n                k = 0\n                while q:\n                    x = q.pop()\n                    k += int(c[x])\n                    c.pop(x)\n                    d.pop(x)\n                    n -= 1\n            else:\n                k = 1\n                while q:\n                    x = q.pop()\n                    k *= int(c[x])\n                    c.pop(x)\n                    d.pop(x)\n                    n -= 1\n            c[j-1] = k\n    print(c[0])\n\"\"\"\n\n#2013_c\n\"\"\"\nfrom collections import defaultdict\n\ndef parse_expr(s,i):\n    i += 1\n    if s[i] == \"[\":\n        q = []\n        while s[i] != \"]\":\n            e,i = parse_expr(s,i)\n            q.append(e)\n        return (calc(q),i+1)\n    else:\n        n,i = parse_num(s,i)\n        return (calc([n]),i+1)\n\ndef parse_num(s,i):\n    m = int(s[i])\n    i += 1\n    while f_num[s[i]]:\n        m *= 10\n        m += int(s[i])\n        i += 1\n    return (m,i)\n\ndef calc(q):\n    if len(q) == 1:\n        return (q[0]+1)//2\n    q.sort()\n    return sum(q[:len(q)//2+1])\n\nf_num = defaultdict(lambda : 0)\nfor i in range(10):\n    f_num[str(i)] = 1\n\nn = int(input())\nfor i in range(n):\n    s = input()\n    print(parse_expr(s,0)[0])\n\"\"\"\n\n#2003_C\n\"\"\"\nwhile 1:\n    w,h = LI()\n    if w == h == 0:\n        break\n    s = SR(h)\n    dp = [[0]*w for i in range(h)]\n    for y in range(h):\n        for x in range(w):\n            if s[y][x].isdecimal():\n                dp[y][x] = max(dp[y-1][x],dp[y][x-1])*10+int(s[y][x])\n    ans = 0\n    for i in dp:\n        ans = max(ans,max(i))\n    print(ans)\n\"\"\"\n#2008_C\n\"\"\"def parse_formula(s,i):\n    if s[i] == \"-\":\n        i += 1\n        e,i = parse_formula(s,i)\n        return 2-e,i\n    elif s[i] == \"(\":\n        i += 1\n        e1,i = parse_formula(s,i)\n        op = s[i]\n        i += 1\n        e2,i = parse_formula(s,i)\n        i += 1\n        return calc(op,e1,e2),i\n    else:\n        return int(s[i]),i+1\n\ndef calc(op,a,b):\n    if op == \"*\":\n        return min(a,b)\n    else:\n        return max(a,b)\n\nwhile 1:\n    s = S()\n    if s[0] == \".\":\n        break\n    t = []\n    f = defaultdict(int)\n    for p in range(3):\n        f[\"P\"] = p\n        for q in range(3):\n            f[\"Q\"] = q\n            for r in range(3):\n                f[\"R\"] = r\n                t.append([f[s[i]] if s[i] in \"PQR\" else s[i] for i in range(len(s))])\n    ans = 0\n    for s in t:\n        if parse_formula(s,0)[0] == 2:\n            ans += 1\n    print(ans)\n\"\"\"\n#2011_C\nd = [(1,0),(-1,0),(0,1),(0,-1)]\ndef dfs(dep,s):\n    global ans\n    if dep == 5:\n        b = bfs(s)\n        m = 0\n        for i in b:\n            m += sum(i)\n        ans = max(ans, m)\n    else:\n        if dep < 4:\n            for i in range(6):\n                b = bfs(s)\n                dfs(dep+1,[[i+1 if b[y][x] else s[y][x] for x in range(w)] for y in range(h)])\n        else:\n            b = bfs(s)\n            dfs(dep+1,[[c if b[y][x] else s[y][x] for x in range(w)] for y in range(h)])\n\ndef bfs(s):\n    b = [[0]*w for i in range(h)]\n    b[0][0] = 1\n    q = deque([(0,0)])\n    while q:\n        y,x = q.popleft()\n        for dy,dx in d:\n            y_ = y+dy\n            x_ = x+dx\n            if 0 <= y_ < h and 0 <= x_ < w:\n                if not b[y_][x_] and s[y_][x_] == s[0][0]:\n                    b[y_][x_] = 1\n                    q.append((y_,x_))\n    return b\n\nwhile 1:\n    h,w,c = LI()\n    if h == 0:\n        break\n    s = LIR(h)\n    ans = 0\n    dfs(0,s)\n    print(ans)\n\n", "from copy import deepcopy\n\nwhile 1:\n    h, w, c = map(int, input().split())\n    if h == w == c == 0:\n        break\n    \n    P = [list(map(int, input().split())) for _ in range(h)]\n    \n    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n    \n    def change(P, c):\n        P = deepcopy(P)\n        stack = [(0, 0)]\n        bc = P[0][0]\n        if bc == c:\n            return P\n        P[0][0] = c\n        while stack:\n            i, j = stack.pop()\n            for di, dj in directions:\n                ni, nj = i + di, j + dj\n                if ni == -1 or nj == -1 or ni == h or nj == w:\n                    continue\n                if P[ni][nj] != bc:\n                    continue\n                P[ni][nj] = c\n                stack.append((ni, nj))\n        return P\n    \n    def dfs(x, P):\n        if x == 4:\n            P = change(P, c)\n            ret = 1\n            stack = [(0, 0)]\n            P[0][0] = -1\n            while stack:\n                i, j = stack.pop()\n                for di, dj in directions:\n                    ni, nj = i + di, j + dj\n                    if ni == -1 or nj == -1 or ni == h or nj == w:\n                        continue\n                    if P[ni][nj] != c:\n                        continue\n                    P[ni][nj] = -1\n                    ret += 1\n                    stack.append((ni, nj))\n            return ret\n        \n        ret = 0\n        bc = P[0][0]\n        for i in range(1, 7):\n            if i != bc:\n                ret = max(ret, dfs(x + 1, change(P, i)))\n        return ret\n    \n    print(dfs(0, P))\n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**10\nmod = 10**9+7\ndd = [(0,-1),(1,0),(0,1),(-1,0)]\nddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]\n\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\n\ndef main():\n    rr = []\n\n\n    while True:\n        h,w,c = LI()\n        if h == 0:\n            break\n        a = [LI() for _ in range(h)]\n        mc = max(map(max,a))\n        d = collections.defaultdict(int)\n        for i in range(h):\n            for j in range(w):\n                d[(i,j)] = a[i][j]\n\n        def f(c,s):\n            ff = True\n            ts = s\n            while ff:\n                r = set()\n                ff = False\n                for i,j in ts:\n                    for di,dj in dd:\n                        ni = i + di\n                        nj = j + dj\n                        if d[(ni,nj)] == c and not (ni,nj) in ts:\n                            ff = True\n                            r.add((ni,nj))\n                ts = ts | r\n            return ts\n\n        r = 0\n        s = f(a[0][0], set([(0,0)]))\n        for ca in itertools.product(range(1,mc+1), repeat=4):\n            ts = s\n            for nc in ca:\n                ts = f(nc, ts)\n            ts = f(c, ts)\n            if r < len(ts):\n                r = len(ts)\n        rr.append(r)\n\n    return '\\n'.join(map(str, rr))\n\n\n\nprint(main())\n\n", "import copy\nimport itertools\nimport sys\n\nif sys.version[0] == '2':\n    range, input = xrange, raw_input\n\ndrc = [(-1, 0), (0, 1), (1, 0), (0, -1)]\nC_NUM = 6\n\n\ndef dfs(r, c, now_c, next_c):\n    tmp_board[r][c] = next_c\n    for dr, dc in drc:\n        nr, nc = r + dr, c + dc\n        if 0 <= nr < H and 0 <= nc < W and tmp_board[nr][nc] == now_c:\n            dfs(nr, nc, now_c, next_c)\n\n\nwhile True:\n    H, W, C = map(int, input().split())\n    if not (H | W | C):\n        break\n    board = [[int(x) - 1 for x in input().split()] for _ in range(H)]\n    ans = 0\n    for ope in itertools.product(range(C_NUM), repeat=4):\n        if ope[0] == board[0][0] or ope[-1] == C - 1 or any(ope[i] == ope[i + 1] for i in range(3)):\n            continue\n        tmp_board = copy.deepcopy(board)\n        for color in ope:\n            dfs(0, 0, tmp_board[0][0], color)\n        dfs(0, 0, tmp_board[0][0], C - 1)\n        dfs(0, 0, tmp_board[0][0], -1)\n        cand = sum(row.count(-1) for row in tmp_board)\n        if cand > ans:\n            ans = cand\n    print(ans)\n", "# Description:\n#     - DFS\u3092\u884c\u3044, \u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u5927\u304d\u3055\u304c\u4f55\u5358\u4f4d\u306b\u5f53\u305f\u308b\u304b\u3092\u6570\u3048\u308b\n# Output:\n#     - \u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u5927\u304d\u3055\ndef count_unit():\n    res = 0 # \u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u5927\u304d\u3055\u3092\u8868\u3059\u5909\u6570res\u3092\u4f5c\u6210\n    seen = [[False]*w for i in range(h)] # \u5404\u5358\u4f4d\u30d1\u30cd\u30eb\u304c\u767a\u898b\u6e08\u307f\u3067\u3042\u308b\u304b\u3092\u8868\u3059\u914d\u5217seen\u3092\u4f5c\u6210\n    seen[0][0] = True # seen[0][0]\u3092True\u306b\u5909\u66f4\n    go = [(0,0)] # \u767a\u898b\u6e08\u307f\u3067\u672a\u63a2\u7d22\u306e\u5358\u4f4d\u30d1\u30cd\u30eb\u3092\u8868\u3059\u914d\u5217go\u3092\u4f5c\u6210\n    while go: # go\u304c\u7a7a\u306b\u306a\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3057\n        i,j = go.pop() # go\u306b\u542b\u307e\u308c\u308b\u8981\u7d20\u306e\u3046\u3061, \u6700\u3082\u9045\u304f\u898b\u3064\u304b\u3063\u305f\u3082\u306e\u3092\u53d6\u308a\u51fa\u3059\n        res += 1 # res\u306b1\u52a0\u7b97\n        for di,dj in d: # d\u306b\u542b\u307e\u308c\u308b\u5168\u3066\u306e\u8981\u7d20\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057(\u5168\u3066\u306e\u79fb\u52d5\u306e\u4ed5\u65b9\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057)\n            if 0 <= di+i < h and 0 <= dj+j < w: # di+i\u304c0\u4ee5\u4e0ah\u672a\u6e80, dj+j\u304c0\u4ee5\u4e0aw\u672a\u6e80\u3067\u3042\u308b\u5834\u5408(\u3053\u306e\u79fb\u52d5\u304c\u53ef\u80fd\u3067\u3042\u308b\u5834\u5408)\n                if not seen[i+di][j+dj] and p[i][j] == p[i+di][j+dj]: # \u79fb\u52d5\u5148\u304c\u672a\u767a\u898b\u304b\u3064, \u540c\u8272\u3067\u3042\u308b\u5834\u5408\n                    go.append((di+i,dj+j)) # go\u306b(di+i,dj+j)\u3092\u8ffd\u52a0\n                    seen[di+i][dj+j] = True # seen[di+i][dj+j]\u3092True\u306b\u5909\u66f4\n    return res # res\u3092\u8fd4\u3059\n\n# Input:\n#     - col:\u5de6\u4e0a\u30d1\u30cd\u30eb\u3092\u4f55\u8272\u306b\u5909\u66f4\u3059\u308b\u304b\u3092\u8868\u3059\u5909\u6570\n#     - rem:\u6b8b\u308a\u4f55\u56de\u8272\u3092\u5909\u66f4\u3059\u308b\u304b\u3092\u8868\u3059\u5909\u6570\n# Description:\n#     - DFS\u3092\u884c\u3044, \u30d1\u30cd\u30eb\u306e\u8272\u3092\u5909\u66f4\u3059\u308b\n#     - \u307e\u305f, \u3053\u306e\u3068\u304d\u306b\u5f97\u3089\u308c\u308b\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u6700\u5927\u306e\u5927\u304d\u3055\u3092\u518d\u5e30\u7684\u306b\u6c42\u3081\u308b\n# Output:\n#     - \u5de6\u4e0a\u30d1\u30cd\u30eb\u3092col\u306b\u5909\u66f4\u3057\u305f\u969b\u306b\u5f97\u3089\u308c\u308b\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u6700\u5927\u306e\u5927\u304d\u3055\ndef paint(col,rem): \n    changed = [] # \u8272\u3092\u5909\u66f4\u3057\u305f\u5358\u4f4d\u30d1\u30cd\u30eb\u3092\u8868\u3059\u914d\u5217changed\u3092\u4f5c\u6210\n    bef = p[0][0] # p[0][0] (\u73fe\u5728\u306e\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u8272) \u3092bef\u3068\u3057\u3066\u4fdd\u5b58\n    go = [(0,0)] # \u767a\u898b\u6e08\u307f\u3067\u672a\u63a2\u7d22\u306e\u5358\u4f4d\u30d1\u30cd\u30eb\u3092\u8868\u3059\u914d\u5217go\u3092\u4f5c\u6210 \n    while go: # go\u304c\u7a7a\u306b\u306a\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3057\n        i,j = go.pop() # go\u306b\u542b\u307e\u308c\u308b\u8981\u7d20\u306e\u3046\u3061, \u6700\u3082\u9045\u304f\u898b\u3064\u304b\u3063\u305f\u3082\u306e\u3092\u53d6\u308a\u51fa\u3059\n        changed.append((i,j)) # changed\u306b(i,j)\u3092\u8ffd\u52a0\n        p[i][j] = col # \u5358\u4f4d\u30d1\u30cd\u30eb\u306e\u8272\u3092col\u306b\u5909\u66f4\n        for di,dj in d: # d\u306b\u542b\u307e\u308c\u308b\u5168\u3066\u306e\u8981\u7d20\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057(\u5168\u3066\u306e\u79fb\u52d5\u306e\u4ed5\u65b9\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057)\n            if 0 <= di+i < h and 0 <= dj+j < w: # di+i\u304c0\u4ee5\u4e0ah\u672a\u6e80, dj+j\u304c0\u4ee5\u4e0aw\u672a\u6e80\u3067\u3042\u308b\u5834\u5408(\u3053\u306e\u79fb\u52d5\u304c\u53ef\u80fd\u3067\u3042\u308b\u5834\u5408)\n                if p[i+di][j+dj] == bef: # p[i+di][j+dj]\u304cbef\u3068\u7b49\u3057\u3044\u5834\u5408(\u3053\u306e\u30d1\u30cd\u30eb\u3082\u8272\u304c\u5909\u5316\u3059\u308b\u5834\u5408)\n                    go.append((di+i,dj+j)) # go\u306b(di+i,dj+j)\u3092\u8ffd\u52a0\n    res = 0 # \u3053\u306e\u6642\u306e\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u6700\u5927\u306e\u5927\u304d\u3055\u3092\u8868\u3059\u5909\u6570res\u3092\u4f5c\u6210\n    if rem == 1: # rem\u304c1\u3067\u3042\u308b\u5834\u5408(\u3053\u308c\u4ee5\u4e0a\u8272\u306e\u5909\u66f4\u3092\u884c\u3048\u306a\u3044\u3068\u304d)\n        res = count_unit() # res\u3092\u73fe\u5728\u306e\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u5927\u304d\u3055\u3068\u3059\u308b\n    elif rem == 2: # rem\u304c2\u3067\u3042\u308b\u5834\u5408(\u6b8b\u308a1\u56de\u3057\u304b\u8272\u3092\u5909\u66f4\u3067\u304d\u306a\u3044\u3068\u304d)\n        if col != c: # \u73fe\u5728\u306e\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u8272\u3068\u76ee\u6a19\u8272\u304c\u7570\u306a\u308b\u5834\u5408\n            res = paint(c,1) # res\u3092 paint(c,1) \u3068\u3059\u308b\n    else: # rem\u304c3\u4ee5\u4e0a\u3067\u3042\u308b\u5834\u5408\n        for i in range(1,7): # 1\u304b\u30896\u307e\u3067\u7e70\u308a\u8fd4\u3057(\u5168\u3066\u306e\u8272\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057)\n            if i != col: # \u73fe\u5728\u306e\u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u8272\u3068i\u304c\u7570\u306a\u308b\u5834\u5408\n                res = max(res,paint(i,rem-1)) # paint(i,rem-1)\u304cres\u3088\u308a\u3082\u5927\u304d\u3044\u5834\u5408, \u5909\u66f4\u3059\u308b\n    for i,j in changed: # changed\u306b\u542b\u307e\u308c\u308b\u5168\u3066\u306e\u8981\u7d20\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057\n        p[i][j] = bef # \u30d1\u30cd\u30eb\u306e\u8272\u3092\u5909\u66f4\u3059\u308b\u524d\u306b\u623b\u3059\n    return res # res\u3092\u8fd4\u3059\n\nd = [(1,0),(-1,0),(0,1),(0,-1)] # \u5168\u3066\u306e\u79fb\u52d5\u306e\u4ed5\u65b9\u3092\u8868\u3059\u914d\u5217d\u3092\u4f5c\u6210\n \nwhile True: # break\u3059\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3057\n    h,w,c = map(int,input().split()) # \u9577\u65b9\u5f62\u306e\u9ad8\u3055h, \u5e45w, \u76ee\u6a19\u3068\u306a\u308b\u8272c\u3092\u5165\u529b\n    if (h,w,c) == (0,0,0): # h,w,c\u304c\u3044\u305a\u308c\u30820\u3067\u3042\u308b\u5834\u5408\n        break # \u89e3\u7b54\u7d42\u4e86\n    p = [] # \u5404\u5358\u4f4d\u30d1\u30cd\u30eb\u306e\u8272\u3092\u8868\u3059\u914d\u5217p\u3092\u4f5c\u6210\n    for i in range(h): # h\u56de\u7e70\u308a\u8fd4\u3057\n        p.append(list(map(int,input().split()))) # \u5358\u4f4d\u30d1\u30cd\u30eb\u306e\u8272\u3092\u5165\u529b\u3057, p\u306b\u4fdd\u5b58\n    ans = 0 # \u5de6\u4e0a\u30d1\u30cd\u30eb\u306e\u6700\u5927\u306e\u5927\u304d\u3055\u3092\u8868\u3059\u5909\u6570ans\u3092\u4f5c\u6210\n    for i in range(1,7): # 1\u304b\u30896\u307e\u3067\u7e70\u308a\u8fd4\u3057(\u5168\u3066\u306e\u8272\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057)\n        if i != p[0][0]: # i\u304cp[0][0]\u3068\u7570\u306a\u308b\u5834\u5408\n            ans = max(ans,paint(i,5)) # paint(i,5)\u304cans\u3088\u308a\u3082\u5927\u304d\u3044\u5834\u5408, \u5909\u66f4\u3059\u308b \n    print(ans) # ans\u3092\u51fa\u529b\n", "from collections import deque\n\np_copy = []\n\n\ndef change(y):\n    global p_copy\n    x = p_copy[0][0]\n    que = deque()\n    que.append((0, 0))\n    memo = {(0, 0): 1}\n    while len(que) > 0:\n        i, j = que.popleft()\n        p_copy[i][j] = y\n        if i + 1 < h and p_copy[i + 1][j] == x and (i + 1, j) not in memo:\n            que.append((i + 1, j))\n            memo[(i + 1, j)] = 1\n        if j + 1 < w and p_copy[i][j + 1] == x and (i, j + 1) not in memo:\n            que.append((i, j + 1))\n            memo[(i, j + 1)] = 1\n        if i - 1 >= 0 and p_copy[i - 1][j] == x and (i - 1, j) not in memo:\n            que.append((i - 1, j))\n            memo[(i - 1, j)] = 1\n        if j - 1 >= 0 and p_copy[i][j - 1] == x and (i, j - 1) not in memo:\n            que.append((i, j - 1))\n            memo[(i, j - 1)] = 1\n\n\ndef count():\n    global p_copy\n    res = 0\n    que = deque()\n    if p_copy[0][0] == c:\n        que.append((0, 0))\n    memo = {(0, 0): 1}\n    while len(que) > 0:\n        i, j = que.popleft()\n        res += 1\n        if i + 1 < h and p_copy[i + 1][j] == c and (i + 1, j) not in memo:\n            que.append((i + 1, j))\n            memo[(i + 1, j)] = 1\n        if j + 1 < w and p_copy[i][j + 1] == c and (i, j + 1) not in memo:\n            que.append((i, j + 1))\n            memo[(i, j + 1)] = 1\n        if i - 1 >= 0 and p_copy[i - 1][j] == c and (i - 1, j) not in memo:\n            que.append((i - 1, j))\n            memo[(i - 1, j)] = 1\n        if j - 1 >= 0 and p_copy[i][j - 1] == c and (i, j - 1) not in memo:\n            que.append((i, j - 1))\n            memo[(i, j - 1)] = 1\n    return res\n\n\n_max = 0\n\n\ndef solve(p, n, before):\n    global _max, p_copy\n    if n == 1:\n        change(c)\n        temp = count()\n        if temp > _max:\n            _max = temp\n        return\n    for k in range(1, 7):\n        if k == before:\n            continue\n        p_copy = [[j for j in i] for i in p]\n        change(k)\n        solve(p_copy, n - 1, k)\n\n\nwhile True:\n    h, w, c = map(int, input().split())\n    if h | w | c == 0:\n        break\n    p_list = [list(map(int, input().split()))for i in range(h)]\n    solve(p_list, 5, -1)\n    print(_max)\n    _max = 0\n", "from collections import defaultdict,deque\nimport sys,heapq,bisect,math,itertools,string,queue,copy,time\nsys.setrecursionlimit(10**8)\nINF = float('inf')\nmod = 10**9+7\neps = 10**-7\ndef inp(): return int(input())\ndef inpl(): return list(map(int, input().split()))\ndef inpl_str(): return list(input().split())\n\ndef dfs(x,y,s,c):\n    global tmpp\n    if not(0<=x<W and 0<=y<H):\n        return\n    elif tmpp[y][x] != s:\n        return\n    else:\n        tmpp[y][x] = c\n        dfs(x+1,y,s,c)\n        dfs(x-1,y,s,c)\n        dfs(x,y+1,s,c)\n        dfs(x,y-1,s,c)\n\ndef calc(x,y):\n    global tmpp\n    if not(0<=x<W and 0<=y<H):\n        return 0\n    elif tmpp[y][x] != C:\n        return 0\n    else:\n        tmpp[y][x] = -1\n        return calc(x+1,y) + calc(x-1,y) + calc(x,y+1) + calc(x,y-1) + 1\n\n\n\nwhile True:\n    H,W,C = inpl()\n    if H == 0:\n        break\n    pp = [inpl() for _ in range(H)]\n    ans = 0\n\n    for arg in itertools.product(range(1,7),repeat=4):\n        colors = list(arg) + [C]\n        tmpp = [p[:] for p in pp]\n        for c in colors:\n            if tmpp[0][0] == c:\n                continue\n            else:\n                dfs(0,0,tmpp[0][0],c)\n\n        ans = max(calc(0,0),ans)\n\n    print(ans)\n\n"]

source: aizu

question:
Identically Colored Panels Connection

Dr. Fukuoka has invented fancy panels.

Each panel has a square shape of a unit size and
has one of the six colors, namely, yellow, pink, red, purple, green and blue.

The panel has two remarkable properties.

One property is that, when two or more panels with the same color
are placed adjacently, their touching edges melt a little
and they are fused each other.
The fused panels are united into a polygonally shaped panel.

The other property is that the color of a panel can be changed
to one of six colors by giving an electrical shock.
The resulting color can be controlled by its waveform.
The electrical shock to an already united panel changes
the color of the whole to a specified single color.

Since he wants to investigate the strength with respect to the
color and the size of a united panel compared to unit panels,
he tries to unite panels into a polygonal panel with a specified color.

![image](1.png)

Figure C-1: panels and their initial colors

Since many panels are simultaneously synthesized and generated on a base plate
through some complex chemical processes,
the fabricated panels are randomly colored and
they are arranged in a rectangular shape on the base plate  (Figure C-1).

Note that the two purple (color 4) panels in Figure C-1 are
already united at the initial state since they are
adjacent to each other.

Installing  electrodes to a panel, and
changing its color several times by giving electrical shocks
according to an appropriate sequence for a specified target color,
he can make a united panel merge the adjacent panels
to unite them step by step
and can obtain a larger panel with the target color.

Unfortunately, panels will be broken when
they are struck by the sixth electrical shock.

That is, he can change the color of a panel or a united panel only
five times.

Let us consider a case
where the panel at the upper left corner of the panel configuration
(Figure C-1) is attached with the electrodes.
First, changing the color of the panel from yellow to blue,
the two adjacent panels are fused into a united panel (Figure C-2).

![image](2.png)

Figure C-2:
Change of the color of the panel at the upper left corner,
from yellow (color 1) to blue (color 6).

Second, changing the color of the upper left united panel from blue
to red, a united red panel that consists of three unit panels is newly formed
(Figure C-3).
Then, changing the color of the united panel from red to purple,
panels are united again to form a united panel of five unit panels
(Figure C-4).

![image](3.png)

Figure C-3:
Change of the color of the panel at the upper left corner,
from blue (color 6) to red (color 3).

![image](4.png)

Figure C-4:
Change of the color of the panel at the upper left corner,
from red (color 3) to purple (color 4).

Furthermore, through making a pink united panel in Figure C-5 by
changing the color from purple to pink,
then, the green united panel in Figure C-6 is obtained
by changing the color from pink to green.
The green united panel consists of ten unit panels.

![image](5.png)

Figure C-5:
Change of the color of the panel at the upper left corner,
from  purple (color 4) to pink (color 2).

![image](6.png)

Figure C-6:
Change of the color of the panel at the upper left corner,
from pink (color 2) to green (color 5).

In order to check the strength of united panels with
various sizes and colors, he needs to unite as many panels
as possible with the target color.

Your job is to write a program that finds a sequence to change
the colors five times
in order to get the largest united panel with the target color.

Note that the electrodes are fixed to the panel at the upper left corner.

Input

The input consists of multiple datasets, each being in the following format.

h w c
p_{1,1} p_{1,2} ... p_{1,w}
p_{2,1} p_{2,2} ... p_{2,w}
...
p_{h,1} p_{h,2} ... p_{h,w}

h and w are positive integers no more than 8 that
represent the height and the width of the given rectangle.
c is a positive integer no more than 6 that represents
the target color of the finally united panel.

p_{i,j} is a positive integer no more than 6
that represents the initial color of the panel at the position
(i, j).

The end of the input is indicated by a line that consists of
three zeros separated by single spaces.

Output

For each dataset, output the largest possible number of unit panels
in the united panel at the upper left corner with the target color
after five times of color changes of the panel
at the upper left corner.
No extra characters should occur in the output.

Sample Input

3 5 5
1 6 3 2 5
2 5 4 6 1
1 2 4 1 5
4 5 6
1 5 6 1 2
1 4 6 3 2
1 5 2 3 2
1 1 2 3 2
1 1 5
1
1 8 6
1 2 3 4 5 1 2 3
8 1 1
1
2
3
4
5
1
2
3
8 8 6
5 2 5 2 6 5 4 2
4 2 2 2 5 2 2 2
4 4 4 2 5 2 2 2
6 4 5 2 2 2 6 6
6 6 5 5 2 2 6 6
6 2 5 4 2 2 6 6
2 4 4 4 6 2 2 6
2 2 2 5 5 2 2 2
8 8 2
3 3 5 4 1 6 2 3
2 3 6 4 3 6 2 2
4 1 6 6 6 4 4 4
2 5 3 6 3 6 3 5
3 1 3 4 1 5 6 3
1 6 6 3 5 1 5 3
2 4 2 2 2 6 5 3
4 1 3 6 1 5 5 4
0 0 0

Output for the Sample Input

10
18
1
5
6
64
33

image_tags: Patterns Patterns Patterns Patterns Patterns Patterns

data_split: test