Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

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

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

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

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 100
• 1 = A_1 < A_2 < \ldots < A_K \leq N
• All values in the input are integers.

Sample Input 1

10 2
1 4

Sample Output 1

5

Below is one possible progression of the game.

• Takahashi removes 4 stones from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 1 stone from the pile.
• Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

• Takahashi removes 1 stone from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 4 stones from the pile.
• Aoki removes 1 stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

8

Below is one possible progression of the game.

• Takahashi removes 6 stones.
• Aoki removes 3 stones.
• Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

Sample Input 3

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

5136

Problem Statement

A box contains N balls, each with an integer between 1 and M-1 written on it. For i = 1, 2, \ldots, N, the integer written on the i-th ball is A_i.

While the box has two or more balls remaining, Takahashi will repeat the following.

• First, choose two balls arbitrarily.
• Then, get a score equal to the remainder when x^y + y^x is divided by M, where x and y are the integers written on the two balls.
• Finally, choose one of the two balls arbitrarily, eat it, and return the other to the box.

Print the maximum possible total score Takahashi will get.

Constraints

• 2 \leq N \leq 500
• 2 \leq M \leq 10^9
• 1 \leq A_i \leq M-1
• All values in the input are integers.

Sample Input 1

4 10
4 2 3 2

Sample Output 1

20

Consider the following scenario. Below, X \bmod Y denotes the remainder when a non-negative integer X is divided by a positive integer Y.

1. Take the first and third balls from the box to score (4^3 + 3^4) \bmod 10 = 5 points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
2. Take the third and fourth balls from the box to score (3^2 + 2^3) \bmod 10 = 7 points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
3. Take the second and fourth balls from the box to score (2^2 + 2^2) \bmod 10 = 8 points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.

Here, Takahashi scores a total of 5 + 7 + 8 = 20 points, which is the maximum possible value.

Sample Input 2

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

Sample Output 2

1733

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

• Placed in row i
• Placed in column j
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i+j=a+b
• Placed on any square (a,b)\ (1\leq a\leq N,1\leq b\leq N) where i-j=a-b

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• 1\leq N\leq10^9
• 1\leq M\leq10^3
• 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
• (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on only two squares: squares (6,6) and (7,7).

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999997000000002

Out of 10^{18} squares, the squares that cannot be used are: squares in row 1, squares in column 1, and squares (1,1), (2,2), \ldots, (10^9,10^9), totaling 3\times10^9-2 squares.

Note that the answer may be 2^{32} or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

77