Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

10 10
4 10 7 2 8 3 9 1 6 5
3 6 2 9 1 8 10 7 4 5
9 3 4 5 7 10 1 8 2 6
7 3 1 8 4 9 5 6 2 10
5 2 1 4 10 7 9 8 3 6
5 8 1 6 9 3 2 4 7 10
8 10 3 4 5 7 2 9 6 1
3 10 2 7 8 5 1 4 9 6
10 6 1 5 4 2 3 8 9 7
4 5 9 1 8 2 7 6 3 10

Sample Output 3

6

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

You are given two grids, A and B, each with H rows and W columns.

For each pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, let (i, j) denote the cell in the i-th row and j-th column. In grid A, cell (i, j) contains the integer A_{i, j}. In grid B, cell (i, j) contains the integer B_{i, j}.

You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:

• Choose an integer i satisfying 1 \leq i \leq H-1 and swap the i-th and (i+1)-th rows in grid A.
• Choose an integer i satisfying 1 \leq i \leq W-1 and swap the i-th and (i+1)-th columns in grid A.

Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.

Here, grid A is identical to grid B if and only if, for all pairs of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, the integer written in cell (i, j) of grid A is equal to the integer written in cell (i, j) of grid B.

Constraints

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

Sample Input 1

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

Sample Output 1

3

Swapping the fourth and fifth columns of the initial grid A yields the following grid:

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

Then, swapping the second and third rows yields the following grid:

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

Finally, swapping the second and third columns yields the following grid, which is identical to grid B:

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

You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print 3.

Sample Input 2

2 2
1 1
1 1
1 1
1 1000000000

Sample Output 2

-1

There is no way to perform the operation to make grid A match grid B, so print -1.

Sample Input 3

3 3
8 1 6
3 5 7
4 9 2
8 1 6
3 5 7
4 9 2

Sample Output 3

0

Grid A is already identical to grid B at the beginning.

Sample Input 4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

Sample Output 4

20