Problem Statement

You are given integers a, b, c, and d. Print two lines as follows.

The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.

Constraints

• -100 \leq a, b, c, d \leq 100
• a, b, c, and d are integers.

Sample Input 1

1 2 5 3

Sample Output 1

6
Takahashi

We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.

Sample Input 2

10 -20 30 -40

Sample Output 2

-700
Takahashi

The input or output may contain negative numbers.

Sample Input 3

100 100 100 -100

Sample Output 3

40000
Takahashi

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

• First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
• Next, choose four integers A, B, C, and D satisfying all of the following.
  • 1 \le A \le B \le 10.
  • 1 \le C \le D \le 10.
• Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
  • A \le i \le B.
  • C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

• S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Sample Input 1

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

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

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

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

• The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
  • That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

• N is an integer.
• 0 \le N < 2^{60}
• In the binary representation of N, at most 15 digit positions contain 1.

Sample Input 1

11

Sample Output 1

0
1
2
3
8
9
10
11

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

• 0000_{(2)}=0_{(10)}
• 0001_{(2)}=1_{(10)}
• 0010_{(2)}=2_{(10)}
• 0011_{(2)}=3_{(10)}
• 1000_{(2)}=8_{(10)}
• 1001_{(2)}=9_{(10)}
• 1010_{(2)}=10_{(10)}
• 1011_{(2)}=11_{(10)}

Sample Input 2

0

Sample Output 2

0

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

• (i-1,j-1)
• (i-1,j)
• (i,j-1)
• (i,j+1)
• (i+1,j)
• (i+1,j+1)

Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

• All values in the input are integers.
• 1 \le N \le 1000
• |X_i|,|Y_i| \le 1000
• The pairs (X_i,Y_i) are distinct.

Sample Input 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

Sample Output 1

3

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

• (-1,-1)
• (1,0),(2,0)
• (0,1),(0,2),(1,2)

Sample Input 2

4
5 0
4 1
-3 -4
-2 -5

Sample Output 2

4

Sample Input 3

5
2 1
2 -1
1 0
3 1
1 -1

Sample Output 3

1

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

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

• For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

• Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
  • A_i \le p \le B_i.
  • C_i \le q \le D_i.

Constraints

• All values in the input are integers.
• 1 \le N,M \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le B_i \le N
• 1 \le C_i \le D_i \le M

Sample Input 1

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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

• The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
• The answer to the second question is 1+0+9+0+17=27.
• The answer to the third question is 17+0+19+0=36.
• The answer to the fourth question is 14.
• The answer to the fifth question is 0.
• The answer to the sixth question is 104.

Sample Input 2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Sample Output 3

712559605
648737448
540261130

Problem Statement

We have N cards numbered 1 to N.
Card i has an integer A_i written on the front and an integer B_i written on the back. Here, \sum_{i=1}^N (A_i + B_i) = M.
For each k=0,1,2,...,M, solve the following problem.

The N cards are arranged so that their front sides are visible. You may choose between 0 and N cards (inclusive) and flip them.
To make the sum of the visible numbers equal to k, at least how many cards must be flipped? Print this number of cards.
If there is no way to flip cards to make the sum of the visible numbers equal to k, print -1 instead.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq A_i, B_i \leq M
• \sum_{i=1}^N (A_i + B_i) = M
• All values in the input are integers.

Sample Input 1

3 6
0 2
1 0
0 3

Sample Output 1

1
0
2
1
1
3
2

For k=0, for instance, flipping just card 2 makes the sum of the visible numbers 0+0+0=0. This choice is optimal.
For k=5, flipping all cards makes the sum of the visible numbers 2+0+3=5. This choice is optimal.

Sample Input 2

2 3
1 1
0 1

Sample Output 2

-1
0
1
-1

Sample Input 3

5 12
0 1
0 3
1 0
0 5
0 2

Sample Output 3

1
0
1
1
1
2
1
2
2
2
3
3
4

Problem Statement

We have a rooted tree T with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is vertex P_i.

A non-empty subset S of the vertex set V = \lbrace 1, 2,\dots, N\rbrace of T is said to be a good vertex set when it satisfies the following condition.

• For every pair of different vertices (u, v) in S, the following holds: u is not an ancestor of v.

For each K = 1, 2, \dots, N, find the number, modulo 998244353, of good vertex sets with exactly K vertices.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \lt i
• All values in the input are integers.

Sample Input 1

4
1 2 1

Sample Output 1

4
2
0
0

For each 1 \leq K \leq N, the good vertex sets of size K are listed below.

• K=1: \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace.
• K=2: \lbrace 2, 4 \rbrace, \lbrace 3, 4 \rbrace.
• K=3,4: There is none.

Sample Input 2

6
1 1 2 2 5

Sample Output 2

6
6
2
0
0
0

Sample Input 3

6
1 1 1 1 1

Sample Output 3

6
10
10
5
1
0

Sample Input 4

10
1 2 1 2 1 1 2 6 9

Sample Output 4

10
30
47
38
16
3
0
0
0
0