Problem Statement

This problem is interactive, and the judge is adaptive. See the notes for details.
Also, the parameters in the problem statement are fixed at N=1000, M=10, Q=950.

There are N coins numbered 1, 2, \dots, N.
Exactly M of these coins are counterfeit.

An appraiser can, in one appraisal, determine whether two coins are of the same type or different types. Specifically:

• If the two coins are both genuine or both counterfeit, they are judged to be of the same type.
• Otherwise, they are judged to be of different types.

Identify all the counterfeit coins using at most Q appraisals.

Constraints

• \color{red}{N = 1000}
• \color{red}{M = 10}
• \color{red}{Q = 950}

Interaction

This is an interactive problem.
Initially, receive N, M, and Q from Standard Input:

N M Q

Next, you can perform appraisals between 0 and Q times, inclusive, as follows.

First, by outputting to Standard Output in the following format, you indicate that you are appraising coins x and y. (Include a newline at the end.)

? x y

Here, x and y must be distinct integers between 1 and N, inclusive.

In response, the judge system will reply with one of the following three responses.

0

If the response is 0, it means that coins x and y are of the same type.

1

If the response is 1, it means that coins x and y are of different types.

-1

If the response is -1, it means that the appraisal is invalid. Specifically, this response is given when at least one of the following conditions is met:

• The outputted x and y does not satisfy the constraints.
• The number of appraisals exceeds Q.

If you receive this response, your program is considered incorrect. Terminate your program immediately.

Finally, by outputting to Standard Output in the following format, you answer that coins A_1, A_2, \dots, A_{M} are counterfeit. (Include a newline at the end.)

! A_1 A_2 \dots A_{M}

Here, A_i must be distinct integers between 1 and N, inclusive.
After this output, terminate your program immediately.

If any of your outputs do not meet the specified format, your program will be considered incorrect. The judge will then respond with -1, so in that case, terminate your program immediately.

Notes

• Every time you output, include a newline at the end and flush Standard Output. Failure to do so may result in a verdict of TLE or WA.
• After outputting your answer (or receiving -1), terminate your program immediately. Otherwise, the verdict is indeterminate.
• Beware that unnecessary newlines are considered as malformed.
• The judge for this problem is adaptive. That is, at any point, as long as consistency can be maintained, the judge may change which coins are counterfeit. See the sample interaction for details.

Sample Interaction

In this interaction, N=5, M=2, Q=10, and the judge initially considers coins 1 and 2 to be counterfeit.

Note that this example does not meet the constraints and is not included in the judge.

Problem Statement

You are given a positive integer N. There is an empty set S, and you can perform the following operation any number of times:

• Choose any positive integer x. For each of x, 2x, and 3x, add it to S if it is not already in S.

Find the minimum number of operations required to satisfy \{1, 2, \dots, N\} \subseteq S.

Constraints

• 1 \leq N \leq 10^{9}

Sample Input 1

7

Sample Output 1

4

Choosing 1, 2, 5, and 7 yields S = \{1, 2, 3, 4, 5, 6, 7, 10, 14, 15, 21\}, which satisfies the condition. It is impossible to satisfy the condition with three or fewer operations.

Sample Input 2

25

Sample Output 2

14

Problem Statement

We have a long, thin piece of paper whose thickness can be ignored. We perform the following operation 100 times: lift the right end, fold it so that it aligns with the left end using the center as a crease. After completing the 100 folds, we unfold the paper back to its original state. At this point, there are 2^{100} - 1 creases on the paper, and these creases can be classified into two types: mountain folds and valley folds. The figure below represents the state after performing the operation twice, where red solid lines represent mountain folds and red dashed lines represent valley folds.

You are given a sequence A = (A_1, A_2, \dots, A_N) of N non-negative integers. Here, 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}.

For each integer i from 1 through 2^{100} - A_N - 1, define f(i) as follows:

• The number of k = 1, 2, \dots, N such that the (i + A_k)-th crease from the left is a mountain fold.

Find the maximum value among f(1), f(2), \dots, f(2^{100} - A_N - 1).

Constraints

• 1 \leq N \leq 10^3
• 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}

Sample Input 1

4
0 1 2 3

Sample Output 1

3

If mountain and valley folds are represented by M and V, respectively, there is a contiguous subsequence of creases like MMVM. There is no contiguous subsequence like MMMM, so the answer is 3.

Sample Input 2

6
0 2 3 5 7 8

Sample Output 2

4

Problem Statement

There are N balls on a two-dimensional plane, numbered from 1 to N. Ball i is at point (X_i, Y_i). Here, X = (X_1, X_2, \dots, X_N) and Y = (Y_1, Y_2, \dots, Y_N) are permutations of (1, 2, \dots, N).

You can perform the following operation any number of times:

• Choose one of the remaining balls, say ball k. Then, for each remaining ball i, if either "X_i < X_k and Y_i < Y_k" or "X_i > X_k and Y_i > Y_k" holds, remove ball i.

Find the number of possible sets of balls remaining after performing operations, modulo 998244353.

Constraints

• 1 \leq N \leq 300
• X and Y are permutations of (1, 2, \dots, N).

Sample Input 1

3
1 3
2 1
3 2

Sample Output 1

3

The possible sets of balls remaining after operations are \{1, 2, 3\}, \{1, 3\}, and \{1, 2\}.

Sample Input 2

4
4 2
2 1
3 3
1 4

Sample Output 2

3

Problem Statement

You are given N length-M sequences, where each element is 0 or 1. The i-th sequence is A_i = (A_{i, 1}, A_{i, 2}, \dots, A_{i, M}).

For integers i, j \ (1 \leq i, j \leq N), define f(i, j) as follows:

• f(i, j) := The smallest non-negative integer x such that A_i and A_j become identical after performing the following operation x times, or 0 if such x does not exist.
  • For all integers k \ (1 \leq k \leq M) simultaneously, replace A_{i, k} with \displaystyle \left (\sum_{l=1}^{k} A_{i, l} \right ) \bmod 2.

Find \displaystyle \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j), modulo 998244353.

Constraints

• 1 \leq N \times M \leq 10^6
• A_{i, j} \in \{0, 1\}

Sample Input 1

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

Sample Output 1

8

f(1, 1) = 0, f(1, 2) = 3, f(1, 3) = 2, f(1, 4) = 0, f(2, 2) = 0, f(2, 3) = 3, f(2, 4) = 0, f(3, 3) = 0, f(3, 4) = 0, f(4, 4) = 0, so print their sum, 8.

Sample Input 2

7 6
1 0 0 0 0 0
1 1 1 0 0 0
1 0 1 1 0 0
1 0 0 0 1 1
1 0 0 0 0 1
1 0 0 0 0 0
1 1 1 1 1 1

Sample Output 2

6