Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.

A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.

Find the index of the best submission.

Constraints

• 1 \leq N \leq 10^5
• S_i is a string consisting of lowercase English characters.
• S_i has a length between 1 and 10, inclusive.
• 0 \leq T_i \leq 10^9
• N and T_i are integers.

Sample Input 1

3
aaa 10
bbb 20
aaa 30

Sample Output 1

2

We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.

Sample Input 2

5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

Sample Output 2

2

Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.

Sample Input 3

10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

Sample Output 3

8

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

• 2 \leq H, W \leq 10
• 1 \leq A_{i, j} \leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
3 2 2
2 1 3
1 5 4

Sample Output 1

3

There are six possible paths:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

48620

In this example, every possible path makes him happy.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell contains one of the characters o, x, and .. The characters written in each cell are represented by H strings S_1, S_2, \ldots, S_H of length W; the character written in cell (i, j) is the j-th character of the string S_i.

For this grid, you may repeat the following operation any number of times, possibly zero:

• Choose one cell with the character . and change the character in that cell to o.

Determine if it is possible to have a sequence of K horizontally or vertically consecutive cells with o written in all cells (in other words, satisfy at least one of the following two conditions). If it is possible, print the minimum number of operations required to achieve this.

• There is an integer pair (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W-K+1 such that the characters in cells (i, j), (i, j+1), \ldots, (i, j+K-1) are all o.
• There is an integer pair (i, j) satisfying 1 \leq i \leq H-K+1 and 1 \leq j \leq W such that the characters in cells (i, j), (i+1, j), \ldots, (i+K-1, j) are all o.

Constraints

• H, W, and K are integers.
• 1 \leq H
• 1 \leq W
• H \times W \leq 2 \times 10^5
• 1 \leq K \leq \max\lbrace H, W \rbrace
• S_i is a string of length W consisting of the characters o, x, and ..

Sample Input 1

3 4 3
xo.x
..o.
xx.o

Sample Output 1

2

By operating twice, for example, changing the characters in cells (2, 1) and (2, 2) to o, you can satisfy the condition in the problem statement, and this is the minimum number of operations required.

Sample Input 2

4 2 3
.o
.o
.o
.o

Sample Output 2

0

The condition is satisfied without performing any operations.

Sample Input 3

3 3 3
x..
..x
.x.

Sample Output 3

-1

It is impossible to satisfy the condition, so print -1.

Sample Input 4

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

Sample Output 4

3