Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

Takahashi keeps a sleep log. The log is represented as an odd-length sequence A=(A _ 1(=0), A _ 2,\ldots,A _ N), where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.

• For every integer i such that 1\leq i\leq\dfrac{N-1}2, he fell asleep exactly A _ {2i} minutes after starting the sleep log and woke up exactly A _ {2i+1} minutes after starting the sleep log.
• He did not fall asleep or wake up at any other time.

Answer the following Q questions. For the i-th question, you are given a pair of integers (l _ i,r _ i) such that 0\leq l _ i\leq r _ i\leq A _ N.

• What is the total number of minutes for which Takahashi was asleep during the r _ i-l _ i minutes from exactly l _ i minutes to r _ i minutes after starting the sleep log?

Constraints

• 3\leq N\lt2\times10^5
• N is odd.
• 0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9
• 1\leq Q\leq2\times10^5
• 0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

Sample Output 1

480
0
960

Takahashi slept as shown in the following figure.

The answers to each question are as follows.

• Between 480 minutes and 1920 minutes after starting the sleep log, Takahashi slept from 480 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 1920 minutes in 3 sleep sessions. The total sleep time is 240+120+120=480 minutes.
• Between 720 minutes and 1200 minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is 0 minutes.
• Between 0 minutes and 2160 minutes after starting the sleep log, Takahashi slept from 240 minutes to 720 minutes, from 1320 minutes to 1440 minutes, and from 1800 minutes to 2160 minutes in 3 sleep sessions. The total sleep time is 480+120+360=960 minutes.

Therefore, the three lines of the output should contain 480, 0, and 960.

Sample Input 2

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

Sample Output 2

296
150
150
49
89
20
279
183
61
177

Problem Statement

This is an interactive task (where your program interacts with the judge's program via input and output).

We have an N-by-N chessboard and N rooks. Below, the square at the i-th row from the top and j-th column from the left is denoted by (i, j).
Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.

• No row contains two or more rooks.
• No column contains two or more rooks.

Now, N-1 rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)

However, you cannot directly see which squares of the chessboard are occupied by a rook.
Instead, you may ask at most 20 questions to the judge in the following manner.

• You choose integers A, B, C, and D such that 1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N, and ask the number of rooks in the rectangular region formed by the squares (i, j) such that A \leq i \leq B, C \leq j \leq D.

Find a square to place a rook.

Constraints

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

Input and Output

This is an interactive task (where your program interacts with the judge's program via input and output).

First, receive the size of the chessboard, N, from Standard Input.

N

Next, repeat asking a question until you find a square to place a rook.
A question should be printed to Standard Output in the following format:

? A B C D

The response will be given from Standard Input in the following format:

T

Here, T is the response to the question, or -1 if the question is invalid or more than 20 questions have been asked.

When the judge returns -1, the submission is already regarded as incorrect. In this case, terminate the program immediately.

When you find a square to place a rook, let (X, Y) be that square and print an answer in the following format. Then, terminate the program immediately.

! X Y

If there are multiple appropriate answers, any of them will be accepted.

Notes

• Each time you print something, end it with a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, the verdict will be indeterminate.
• Terminate the program immediately after printing an answer. Otherwise, the verdict will be indeterminate.

Sample Interaction

Below is an interaction where N=3 and the rooks are placed on (1, 2) and (2, 1).

Problem Statement

You are given a matrix A whose elements are non-negative integers. For a pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, let A_{i, j} denote the element at the i-th row and j-th column of A.

Let us perform the following procedure on A.

• First, replace each element of A that is 0 with an arbitrary positive integer (if multiple elements are 0, they may be replaced with different positive integers).

• Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).

  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq H and swap the i-th and j-th rows of A.
  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq W and swap the i-th and j-th columns of A.

Determine whether A can be made to satisfy the following condition.

• A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}.

• In other words, for every two pairs of integers (i, j) and (i', j') such that 1 \leq i, i' \leq H and 1 \leq j, j' \leq W, both of the following conditions are satisfied.

  • If i \lt i', then A_{i, j} \leq A_{i', j'}.
  • If i = i' and j \lt j', then A_{i, j} \leq A_{i', j'}.

Constraints

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

Sample Input 1

3 3
9 6 0
0 4 0
3 0 3

Sample Output 1

Yes

One can perform the operations as follows to make A satisfy the condition in the problem statement, so you should print Yes.

• First, replace the elements of A that are 0, as shown below:

9 6 8
5 4 4
3 1 3

• Swap the second and third columns. Then, A becomes:

9 8 6
5 4 4
3 3 1

• Swap the first and third rows. Then, A becomes:

3 3 1
5 4 4
9 8 6

• Swap the first and third columns. Then, A becomes the following and satisfies the condition in the problem statement.

1 3 3
4 4 5
6 8 9

Sample Input 2

2 2
2 1
1 2

Sample Output 2

No

There is no way to perform the operations to make A satisfy the condition in the problem statement, so you should print No.