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.

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 5
7 8
3 7

Sample Output 1

2

The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

Sample Input 2

3
3 4
2 5
1 6

Sample Output 2

3

Sample Input 3

2
1 2
3 4

Sample Output 3

0

Problem Statement

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

Initially, there is a slime with strength S _ {i,j} in cell (i,j), and Takahashi is the slime in the cell (P,Q).

Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):

• Among the slimes adjacent to him, choose one whose strength is strictly less than \dfrac{1}{X} times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi's strength increases by the strength of the absorbed slime.

When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).

Constraints

• 1\leq H,W\leq500
• 1\leq P\leq H
• 1\leq Q\leq W
• 1\leq X\leq10^9
• 1\leq S _ {i,j}\leq10^{12}
• All input values are integers.

Sample Input 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

Sample Output 1

28

Initially, the strength of the slime in each cell is as follows:

For example, Takahashi can act as follows:

• Absorb the slime in cell (2,1). His strength becomes 9+4=13, and the slimes in cells (1,1) and (3,1) become newly adjacent to him.
• Absorb the slime in cell (1,2). His strength becomes 13+6=19, and the slime in cell (1,3) becomes newly adjacent to him.
• Absorb the slime in cell (1,3). His strength becomes 19+9=28.

After these actions, his strength is 28.

No matter how he acts, it is impossible to get a strength greater than 28, so print 28.

Note that Takahashi can only absorb slimes whose strength is strictly less than half of his strength. For example, in the figure on the right above, he cannot absorb the slime in cell (1,1).

Sample Input 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

Sample Output 2

5

He cannot absorb any slimes.

Sample Input 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

Sample Output 3

1343

Problem Statement

There is a simple graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertices u_i and v_i.
Each vertex has one lamp on it. Initially, all the lamps are off.

Determine whether it is possible to turn exactly K lamps on by performing the following operation between 0 and M times, inclusive.

• Choose one edge. Let u and v be the endpoints of the edge. Toggle the states of the lamps on u and v. That is, if the lamp is on, turn it off, and vice versa.

If it is possible to turn exactly K lamps on, print a sequence of operations that achieves this state.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
• 0 \leq K \leq N
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

• Choose edge 3. Turn on the lamps on vertex 2 and vertex 4.
• Choose edge 4. Turn on the lamps on vertex 3 and vertex 5.
• Choose edge 5. Turn on the lamp on vertex 1 and turn off the lamp on vertex 5.

After completing all operations, the lamps on vertices 1, 2, 3, and 4 are on. Therefore, this sequence of operations satisfies the conditions.

Other possible sequences of operations that satisfy the conditions include X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1). (It is allowed to choose the same edge more than once.)

Sample Input 2

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

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes
3
10 9 6