Little D has discovered that strings generated by some concise functions possess certain pseudo-random properties. See if you think he is right!

For a $k$-ary function $f$ and $m$ $k$-tuples $x_{i,j}$ ($0 \le i < m, 0 \le j < k$) with values in $[0, n - 1]$, we define the corresponding $n, m$ pseudo-random function $\{0, 1\}^n \to \{0, 1\}^m$ as follows: given an input $(y_0, y_1, \dots, y_{n-1}) \in \{0, 1\}^n$, the output is $(\hat{y}_0, \hat{y}_1, \dots, \hat{y}_{m-1}) \in \{0, 1\}^m$, where $$\hat{y}_i = f(y_{x_{i,0}}, y_{x_{i,1}}, \dots, y_{x_{i,k-1}})$$

Consider the following class of $k$-ary functions $f$: for a sequence of $k-1$ binary operators $[op_0, op_1, \dots, op_{k-2}]$, where $op_i \in \{0, 1, 2\}$ ($0 \le i \le k-2$) represent the binary operators $AND, OR, XOR$ respectively, the corresponding $k$-ary function is defined as: $$(z_0, z_1, \dots, z_{k-1}) \to ((z_0 \ op_0 \ z_1) \ op_1 \ \dots) \ op_{k-2} \ z_{k-1}$$

Given $n, m, k$ and the sequence of $k-1$ binary operators $[op_0, op_1, \dots, op_{k-2}]$, let $f$ be the $k$-ary function corresponding to this sequence. It is guaranteed that $m = 3n$, $k \in \{2, 3, 4\}$, and $op_0, op_1, \dots, op_{k-2}$ are not all $2$.

Little D believes that for $x_{i,j}$ ($0 \le i < m, 0 \le j < k$) chosen independently and uniformly at random from the set of $k$-tuples of distinct integers in $[0, n - 1]$, the $n, m$ pseudo-random function defined by $f$ and $x$ is indistinguishable from an independent uniform random function. You believe his claim is wrong. To prove this, Little D will ask you 100 questions. Each time, he will first generate $x_{i,j}$ ($0 \le i < m, 0 \le j < k$) independently and uniformly at random from the set of $k$-tuples of distinct integers in $[0, n - 1]$, let $\hat{f}$ be the $n, m$ pseudo-random function defined by $f$ and $x$, and then with $50\%$ probability each, choose one of the following two ways to generate $c$ $m$-tuples $s_0, s_1, \dots, s_{c-1}$:

1. Generate $c$ $m$-tuples $s_0, s_1, \dots, s_{c-1}$ independently and uniformly at random from $\{0, 1\}^m$.
2. Generate $c$ $n$-tuples $t_0, t_1, \dots, t_{c-1}$ independently and uniformly at random from $\{0, 1\}^n$, then set $s_i = \hat{f}(t_i)$ ($0 \le i < c$).

You need to determine which method Little D used to generate the $c$ $m$-tuples. Since true randomness can produce any string, you only need to correctly identify the generation method as often as possible.

Implementation Details

You do not need to, and should not, implement a main function.

Your submitted program must include the header file prg.h. You can implement the following function:

int solve(int n, int m, int k, std::vector<int> op,
std::array<std::vector<int>, 3000> x, int c,
std::array<std::array<int, 3000>, 25> s);

• The variables above are defined as in the problem, with $n = 1000$, $m = 3000$, $k \in \{2, 3, 4\}$, and $c = 25$.
• It is guaranteed that the length of $op$ is $k-1$, $op_i \in \{0, 1, 2\}$ ($0 \le i \le k-2$), and $op_0, op_1, \dots, op_{k-2}$ are not all $2$.
• It is guaranteed that each element in $x$ has length $k$, and each element is chosen independently and uniformly at random from the set of $k$-tuples of distinct integers in $[0, n - 1]$.
• It is guaranteed that $s$ is generated by one of the two methods described in the problem.
• You need to return $u \in \{1, 2\}$ representing your answer, where returning $1$ means you believe $s$ was generated by the first method, and returning $2$ means you believe $s$ was generated by the second method.
• For each test case, it is guaranteed that this function will be called exactly 100 times by the interactor.
• The interactor is guaranteed to run within 300 ms and use no more than 32 MiB of memory.

Subtasks

For all test data, it is guaranteed that: $n = 1000, m = 3000, k \in \{2, 3, 4\}, c = 25$. The length of $op$ is $k-1$, $\forall 0 \le i \le k-2, op_i \in \{0, 1, 2\}$, and $op_0, op_1, \dots, op_{k-2}$ are not all $2$. Each element in $x$ has length $k$, and each element is chosen independently and uniformly at random from the set of $k$-tuples of distinct integers in $[0, n - 1]$. $s$ is generated by one of the two methods described in the problem.

Special Property: Each time a query is made, $op$ is chosen independently and uniformly at random from the set of sequences of length $k-1$ that are not all $2$.

Note

• You should not attempt to obtain internal information about the interactor through illegal means, such as attempting to read values stored in the interactor directly or interacting directly with standard input/output streams. Such behavior will be considered cheating.
• The final grading interactor and the sample interactor may differ in implementation; therefore, your solution should not rely on the specific implementation of the interactor.
• This problem is subject to the same constraints as traditional problems; for example, compilation errors will result in 0 points, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test case. You may only access variables defined by yourself or provided by the interactor and their corresponding memory space; attempting to access other memory may result in compilation or runtime errors.
• On the basis of the above conditions: For each test case, if you output the wrong answer for $x$ out of 100 groups, the score for that test case will be $s \times \max(0, 1 - \frac{1}{4} \log_2(\max(x, 1)))$, where $s$ is the score for that test case's subtask. Note that even if $x=1$, you will still receive full marks for this test case.
• There are multiple subtasks in this problem, and each subtask contains exactly 20 test cases. The score for each subtask is the minimum score among the test cases in that subtask.

Examples

The expected value $E$ of the ratio between your score in a subtask and the total score of that subtask is related to the probability $p$ that your code passes a group of data. Through numerical simulation, we can obtain the following (for reference only):

• When $p = 0.95$, $E$ is approximately $0.2$.
• When $p = 0.98$, $E$ is approximately $0.4$.
• When $p = 0.99$, $E$ is approximately $0.6$.
• When $p = 0.995$, $E$ is approximately $0.75$.
• When $p = 0.999$, $E$ is approximately $0.98$.

Note

After you solve this problem, you will find that what Little D said makes no sense!