Problem Statement

In the ceremony commemorating ABC400, we want to arrange 400 people in a rectangular formation of A rows and B columns without any gaps.

You are given a positive integer A. Print the value of a positive integer B for which such an arrangement is possible. If there is no such positive integer B, print -1.

Constraints

• A is an integer between 1 and 400, inclusive.

Sample Input 1

10

Sample Output 1

40

We can arrange 400 people in 10 rows and 40 columns.

Sample Input 2

11

Sample Output 2

-1

Sample Input 3

400

Sample Output 3

1

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq D \leq 100
• There is an arithmetic sequence with first term A, last term B, and common difference D.
• All input values are integers.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

10

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

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

Each cell is painted with one color, white or black. The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.

Determine whether the grid satisfies the following condition:

• For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.

Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.

Constraints

• 1\le H\le 20
• 1\le W\le 20
• H and W are integers.
• S _ i is a string of length W consisting of . and # (1\le i\le H).

Sample Input 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

Sample Output 1

Yes

For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.

Every other black cell also satisfies the condition, so output Yes.

Sample Input 2

1 2
##

Sample Output 2

No

Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.

Therefore, output No.

Sample Input 3

4 3
...
...
...
...

Sample Output 3

Yes

There are no black cells, so the condition is satisfied.

Therefore, output Yes.

Sample Input 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

Sample Output 4

Yes

Problem Statement

This is an interactive problem (in which your program and the judge program communicate via Standard Input and Output).

On a number line, points 1, 2, \ldots, N are arranged from left to right in that order.

Initially, you are given only the integer N.

Then, you can ask the judge the following question at most \bm{2N} times.

• Choose integers i and j satisfying 1 \leq i < j \leq N, and ask whether the distance between points i and j is at most 1.

Output the number of pairs of points whose distance is at most 1, that is, the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that the distance between points i and j is at most 1.

Constraints

• 2 \leq N \leq 10^3
• N is an integer.

Interaction

First, receive the integer N representing the number of points from Standard Input:

N

Then, you can repeat the question described in the problem statement to the judge at most 2N times.

Output the question to Standard Output in the following format, where i and j must be integers satisfying 1 \leq i<j \leq N:

? i j

As a response to this, one of the following will be given from Standard Input:

Yes

No

Here, Yes indicates that the distance between points i and j is at most 1, and No indicates that the distance between points i and j is greater than 1.

Once you have found the answer X to the problem, output your answer in the following format, and then terminate the program immediately:

! X

Notes

• Each time you output something, insert a newline at the end and flush Standard Output. Otherwise, the judge result may be TLE.
• The judge result is indeterminate if you output something invalid during the interaction, or if the program terminates prematurely.
• Terminate the program immediately after outputting your answer. Otherwise, the judge result is indeterminate.
• The arrangement of the points and the answer are fixed at the start of the interaction between you and the judge, and do not change depending on, for example, the questions you make.

Sample Interaction

Below is an example of interaction where N = 3 and the coordinates of points 1,2,3 are 0, 0.7, 1.5, respectively. (The coordinates of points 1,2,3 are not given as input.)

The number of questions is 3, which is in particular at most 2N=6.
Since the answered number of pairs is also correct, the program will be judged as correct if it terminates immediately after this.