Problem Statement

For a positive integer x, let f(x) be the answer to the question below.

The following operation on x can be performed zero or more times.

• Let x' be the integer obtained by reversing the decimal notation of x. Then, replace x with x'. If x now has one or more leading zeros, delete them so that it begins with a non-zero digit.

For example, from x=1420, you get x=241 after one operation, x=142 after two operations, and x=241 after three operations.
Find the minimum possible value of x after operations.

Find the number of integers x such that 1 \leq x \leq N and f(x)=K.

Constraints

• 1 \leq N,K \leq 10^{12}
• All values in input are integers.

Sample Input 1

1420 142

Sample Output 1

3

Three integers x=142, 241, and 1420 satisfy 1 \leq x \leq 1420 and f(x)=142.

Sample Input 2

1419 142

Sample Output 2

2

Sample Input 3

6 19

Sample Output 3

0

Problem Statement

We have an N \times N grid. Let (i,j) denote the square at the i-th row from the top and j-th column from the left in this grid.
Find one way to write an integer on every square to satisfy the conditions below.

• Each integer between 1 and N^2 is written exactly once.
• For every pair of integers i,j\, (1 \leq i,j \leq N), the square (i,j) satisfies the following.
  • Among the squares horizontally, vertically, or diagonally adjacent to (i,j) (there are at most eight of them), let a and b be the number of squares with integers larger than and smaller than that of (i,j), respectively. Then, a \neq b holds.

Under the Constraints of this problem, it can be proved that such a way to write integers always exists.

Constraints

• 2 \leq N \leq 500
• N is an integer.

Sample Input 1

2

Sample Output 1

1 2
3 4

This output contains each integer between 1 and N^2\, (=4) exactly once, so the first condition is satisfied.
Additionally, among the squares horizontally, vertically, or diagonally adjacent to the square (1,1), three squares (1,2), (2,1), and (2,2) have integers larger than that of (1,1), and none has an integer smaller than that.
Thus, for (1,1), we have a=3 and b=0, so a\neq b holds.
Similarly, it can be verified that a\neq b also holds for the other squares, so the second condition is satisfied.
Therefore, this output is valid.

Sample Input 2

3

Sample Output 2

1 2 3
5 4 6
7 8 9

Problem Statement

There is a tree with N vertices, numbered 1, \ldots, N.
For each pair of integers u,v\, (1 \leq u,v \leq N), the distance d_{u,v} between Vertices u, v is defined as the following.

• The number of edges contained in the shortest path connecting Vertices u and v.

You are allowed to ask between 0 and 2N questions (inclusive) in the following form.

• Ask the distance d_{u,v} between Vertices u,v for integers u,v of your choice such that 1\leq u,v \leq N and u+v>3.

Find the distance d_{1,2} between Vertices 1,2.

Constraints

• 3 \leq N \leq 100
• N is an integer.
• The tree is determined before the start of the interaction between your program and the judge.

Input and Output

This is an interactive task, in which your program and the judge interact via input and output.

First, your program is given a positive integer N from Standard Input:

N

Then, you get to ask questions.
A question should be printed in the following format (with a newline at the end):

? u v

If the question is valid, the response d_{u,v} is given from Standard Input:

d_{u,v}

If the question is judged invalid because, for example, it is malformed or you have asked too many questions, you get -1 instead of the response:

-1

At this point, your submission is already judged incorrect. The judge's program then terminates; yours should too, desirably.

When you find the answer d_{1,2}, print it to Standard Output in the following format (with a newline at the end):

! d_{1,2}

Notices

• Flush Standard Output after each output. Otherwise, you might get the TLE verdict.
• After printing the answer (or receiving -1), immediately terminate the program normally. Otherwise, the verdict would be indeterminate.
• The verdict for the case of a malformed output would be indeterminate.
• Specifically, note that too many newlines would also be seen as a malformed output.

Sample Input and Output

The following is a sample interaction for the tree shown in this image.

Problem Statement

We have a tree with N vertices, numbered 1, \ldots, N. For each i=1,\ldots,N-1, the i-th edge connects Vertex a_i and Vertex b_i.
An operation on this tree when at most one piece is put on each vertex is defined as follows.

• Simultaneously move every piece to one of the vertices adjacent to the one occupied by the piece.

An operation is said to be good when the conditions below are satisfied.

• Each edge is traversed by at most one piece.
• Each vertex will be occupied by at most one piece after the operation.

Takahashi will put a piece on one or more vertices of his choice. Among the 2^N-1 ways to put pieces, find the number of ones that satisfy the condition below, modulo 998244353.

• For every non-negative integer K, the following holds.
  • It is possible to perform a good operation K times.
  • Let S_K be the set of vertices occupied by pieces just after K good operations. Then, S_K is unique.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2
1 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

• Put a piece on Vertex 1 and Vertex 2.
• Put a piece on Vertex 1 and Vertex 3.

Note that he must put a piece on at least one vertex.

Sample Input 2

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

Sample Output 2

0

There might be no way to satisfy the condition.

Sample Input 3

19
9 14
2 13
1 3
17 19
13 18
12 19
4 5
2 10
4 9
8 11
3 15
6 8
8 10
6 19
9 13
11 15
7 17
16 17

Sample Output 3

100

Problem Statement

There are N wizards, numbered 1, \ldots, N.
Wizard i has a strength of a_i and plans to defeat a monster with a strength of b_i.

You can perform the following operation any number of times.

• Increase the strength of any wizard of your choice by 1.

A pair of Wizard i and Wizard j (let us call this pair (i, j)) is said to be good when at least one of the following conditions is satisfied.

• Wizard i has a strength of at least b_i and Wizard j has a strength of at least b_j.
• Wizard i has a strength of at least b_j and Wizard j has a strength of at least b_i.

Your objective is to make the pair (x_i, y_i) good for every i=1, \ldots, M.
Find the minimum number of operations needed to achieve it.

Constraints

• 2 \leq N \leq 100
• 1 \leq a_i,b_i \leq 100
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq x_i \lt y_i \leq N
• (x_i,y_i) \neq (x_j,y_j), if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2

You can perform the operation once for Wizard 1 and once for Wizard 4 to achieve the objective with the fewest operations.

Sample Input 2

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

Sample Output 2

0

No operation is needed.

Sample Input 3

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

Sample Output 3

22

Problem Statement

Two wizards, X and Y, are fighting with a monster.

Initially, each of the wizards has a magic power of 0. They know the following two spells.

• Spell 1: Increases the caster's magic power by 1.
• Spell 2: Deals damage equal to the caster's magic power to the monster.

After each wizard uses a spell N times, they will withdraw from the battle.
For each i=1, \ldots, N, they must use one of the following combinations of spells for their i-th spells.

• X casts Spell a_i, and Y casts Spell b_i.
• X casts Spell c_i, and Y casts Spell d_i.

Find the maximum total damage that can be dealt to the monster before the withdrawal.

Constraints

• 1 \leq N \leq 8000
• a_i,b_i,c_i,d_i \in \{1,2\}
• All values in input are integers.

Sample Input 1

3
1 1 2 2
2 1 2 2
2 1 1 1

Sample Output 1

3

The maximum total damage can be achieved as follows.

• As the 1-st spells, use a_1=1,\, b_1=1, increasing both X's and Y's magic powers to 1.
• As the 2-nd spells, use c_2=2,\, d_2=2, dealing 2 points of damage in total.
• As the 3-rd spells, use a_3=2,\, b_3=1, dealing 1 point of damage by X's spell and increasing Y's magic power to 2.

Sample Input 2

5
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2

Sample Output 2

0

Casting Spell 2 with a magic power of 0 deals no damage.

Sample Input 3

8
1 1 2 2
2 2 2 1
1 1 2 1
1 1 2 2
2 1 1 1
1 2 1 2
2 1 1 2
2 1 2 1

Sample Output 3

20

Sample Input 4

20
2 1 2 1
2 1 1 1
1 2 1 1
2 2 1 2
2 2 2 1
1 1 2 1
1 2 2 2
2 2 2 1
1 1 1 2
1 2 1 2
1 2 2 2
2 1 1 2
2 1 1 1
1 2 1 2
1 2 1 2
1 1 1 2
1 1 2 1
2 2 1 1
1 2 2 2
2 1 1 2

Sample Output 4

138