Problem Statement

There are N choices.

You will choose one of these choices. If you choose the i-th choice, your happiness will be X_i.

If your happiness will be negative no matter which choice you choose, output Yes; otherwise, output No.

Constraints

• 2 \leq N \leq 10
• -100 \leq X_i \leq 100
• All input values are integers.

Sample Input 1

4
2 0 -1 2

Sample Output 1

No

If you choose choice 1, 2, or 4, the happiness will not be negative.

Sample Input 2

3
-5 -2 -1

Sample Output 2

Yes

Sample Input 3

4
0 -2 0 -1

Sample Output 3

No

Problem Statement

There are N balls.

The color of the i-th ball is C_i, and its size is S_i. Here, the colors are represented by integers 1, 2, \ldots, M.

For k = 1, 2, \ldots, M, output the maximum size of a ball of color k, or -1 if there is no ball of color k.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq C_i \leq M
• 1 \leq S_i \leq 100
• All input values are integers.

Sample Input 1

4 5
1 3
2 10
1 7
4 9

Sample Output 1

7 10 -1 9 -1

The maximum size of a ball of color 1 is 7, that of a ball of color 2 is 10, and that of a ball of color 4 is 9.

There is no ball of color 3 or color 5.

Sample Input 2

5 5
2 6
5 12
5 2
5 9
2 7

Sample Output 2

-1 7 -1 -1 12

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

There is a grid with N rows and N columns.

Initially, nothing is placed on the grid.
Starting from this state, Takahashi performs M operations on the grid in order. The i-th operation (1\leq i\leq M) is as follows.

• Remove all pieces placed on the cells in the R_i-th row from the top.
• Next, remove all pieces placed on the cells in the C_i-th column from the left.
• Finally, place a piece on the cell at the R_i-th row from the top and the C_i-th column from the left.

Output the number of pieces placed on the grid after the M operations.

Constraints

• 1 \leq N \leq 3\times 10^5
• 1 \leq M \leq 3\times 10^5
• 1 \leq R_i \leq N
• 1 \leq C_i \leq N
• All input values are integers.

Sample Input 1

3 6
1 1
1 2
3 3
3 2
1 3
1 3

Sample Output 1

2

Initially, nothing is placed on the grid with three rows and three columns, and pieces are removed and placed by each operation as follows.
Below, the cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j).

• In the first operation, a piece is placed on cell (1,1).
• In the second operation, the piece is removed from cell (1,1), and a piece is placed on cell (1,2).
• In the third operation, a piece is placed on cell (3,3).
• In the fourth operation, the pieces are removed from cell (1,2) and cell (3,3), and a piece is placed on cell (3,2).
• In the fifth operation, a piece is placed on cell (1,3).
• In the sixth operation, the piece is removed from cell (1,3), and a piece is placed on cell (1,3) again.

In the final state, there is one piece each on cell (1,3) and cell (3,2), so output 2.

Sample Input 2

2 3
1 2
2 1
1 1

Sample Output 2

1

Problem Statement

There are N cards lined up. The cards are numbered 1, 2, \ldots, N.

On the front side of card i, an integer A_i is written, and on the back side, an integer B_i is written. Initially, every card is facing front side up.

You can perform the following operation at most K times.

• Choose integers l and r satisfying 1 \leq l \leq r \leq N. For each integer i satisfying l \leq i \leq r, flip card i. Here, flipping a card means turning the side that was facing down before the operation to face up.

After finishing the operations, find the maximum possible value of the sum of the numbers written on the side of the cards that is facing up.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

45

If you choose l = 2, r = 5 in the first operation and l = 4, r = 4 in the second operation, the numbers written on the side facing up, in order of the card numbers, become 2, 9, 5, 9, 8, 7, 5, and their sum is 45.

Sample Input 2

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

Sample Output 2

35

It is fine if you perform no operation.

Sample Input 3

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

Sample Output 3

47

Problem Statement

You are given integers N,X and a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N).

For a non-negative integer x, define f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N.

Find the number of integers x between 1 and X, inclusive, such that f(x)=0.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 2\times 10^5
• 1\le N\le 2\times 10^5
• The sum of N over all test cases is at most 2\times 10^5.
• 1\le X\le 10^{18}
• 1\le A_i\le 10^{18}
• All input values are integers.

Sample Input 1

4
3 7
5 2 3
9 31415
9 9 8 2 4 4 3 5 3
1 1000000000000000000
1
9 20260405
3141 5926 5358 9793 2384 6264 3383 2795 288

Sample Output 1

4
17452
1000000000000000000
77403

Consider the first test case.

For example, when x=7, f(7)=(((7 \bmod 5) \bmod 2)\bmod 3)=(2\bmod 2)\bmod 3=0\bmod 3=0.

There are four integers x between 1 and 7 such that f(x)=0: x=2,4,5,7.

Problem Statement

You are given M triples of integers (L_i,R_i,S_i).
Consider tuples A=(A_1,A_2,\ldots,A_N) of N positive integers satisfying all of the following conditions.

• The sum of A_{L_i}, A_{L_i+1}, \ldots, A_{R_i} is S_i.

If there are infinitely many tuples satisfying the conditions, output Infinity; otherwise, output the number of such tuples, modulo 998244353.

Constraints

• 1 \leq N \leq 8
• 1 \leq M \leq 36
• 1\leq L_i\leq R_i\leq N
• 1\leq S_i\leq 10^9
• All (L_i,R_i) are distinct.
• All input values are integers.

Sample Input 1

3 2
1 2 7
2 3 10

Sample Output 1

6

We have the following two conditions.

• A_1+A_2=7
• A_2+A_3=10

The six tuples A=(1,6,4), (2,5,5), (3,4,6), (4,3,7), (5,2,8), (6,1,9) satisfy the conditions, so output 6 modulo 998244353, that is, output 6.

Sample Input 2

2 1
1 1 10

Sample Output 2

Infinity

There are infinitely many tuples A satisfying the conditions.

Sample Input 3

2 2
1 1 10
1 2 1

Sample Output 3

0

There is no tuple A satisfying the conditions.