This is an interactive problem.

On the AutoLab platform, there is a strange $k$-bit computer, where $k$ is a fixed constant $8192 = 2^{13}$. The word length of this computer is exactly $\frac{k}{8} = 1024 = 2^{10}$, and it stores integers in the following way:

Each integer is stored in $k$ consecutive bits. Let $S$ be the 01-string of length $k$ obtained by arranging the values of these $k$ consecutive bits in increasing order of their indices. Assuming the indices of $S$ start from $0$, the integer value corresponding to this string $S$ is $f(S) = \sum \limits_{i=0}^{k-1} [S_i==1] sgn_i 2^i$, where $sgn$ is an array of length $k$ predefined by Little W, with indices starting from $0$ and $\forall 0 \le i < k, sgn_i \in \{-1, 1\}$. For some special reasons, this computer guarantees $sgn_{k-1} = 1$ and $sgn_{k-2} = -1$. However, you do not know the values of $sgn_0, sgn_1, \dots, sgn_{k-3}$.

Let $L = \sum \limits_{i=0}^{k-1} \min\{0, sgn_i\} 2^i$ and $R = \sum \limits_{i=0}^{k-1} \max\{0, sgn_i\} 2^i$. It can be shown that for every $x$ such that $L \le x \le R$, there exists exactly one 01-string $T$ of length $k$ such that $f(T) = x$ (proof omitted). Let $S$ be the set of all integers in $[L, R]$. Then $f$ is a bijection from $\{0, 1\}^k$ to $S$. Accordingly, we can assume the inverse function $g(x)$ of $f(x)$ exists, satisfying $\forall x \in S, f(g(x)) = x$.

Given $x, y \in S$, the addition $\oplus$ between two integers on this computer is defined as $x \oplus y \overset{def}{=} (x + y - L + 2^k) \bmod 2^k + L$. It is easy to see that $\forall x, y \in S, x \oplus y \in S$. Thus, addition on this computer satisfies closure. The addition defined by the above rule also satisfies properties such as commutativity and associativity. Proofs of these properties are also omitted.

Students can obtain information related to $sgn_i$ through a limited number of queries. In each query, you can provide the computer with two 01-strings $x$ and $y$ of length $k$, and the computer will return the value of $g(f(x) \oplus f(y))$. The task is to determine the exact values of $sgn_0, sgn_1, \dots, sgn_{k-3}$ using no more than $m$ queries.

Little Z is a brilliant student who tried to calculate the interaction values manually using his $10^3 \mathrm{Hz}$ super-brain. However, he found that his processing speed could not keep up with the massive scale of the data. Therefore, he asks you to write a program to help him complete the assignment more quickly.

Task

This problem only supports C++.

You need to include the header file datalab.h.

You do not need to, and should not, implement the main function. You only need to implement the following function:

1. std::vector<int> solve(int k, int m):
   • The parameters passed are the computer's word length $k$ and the query limit $m$.
   • You need to return a vector of size $k$, where the $i$-th element represents the value of $sgn_i$ you have determined.

You can call the addition operation on Autolab using the following function:

1. std::bitset<8192> Add(std::bitset<8192> x, std::bitset<8192> y):
   • Given two bitsets of size $k$, where each bitset represents a 01-string of length $k$ read from the lowest bit to the highest bit.
   • Returns a bitset of size $k$ representing the value of $g(f(x) \oplus f(y))$. The return format is the same as the input format.

According to the problem requirements, you can query the addition result of two integers on this computer at most $m$ times. That is, you can call the Add function at most $m$ times.

During evaluation, the interaction library will call solve exactly once.

This problem guarantees that the array sgn is fully determined before the start and will not be constructed dynamically based on the interaction with your program. Therefore, the interaction operations are deterministic, and you do not need to worry about the specific implementation of these operations in the interaction library.

It is guaranteed that the time required for the interaction library to run within the query limit does not exceed 1s; the memory used by the interaction library is fixed and does not exceed 128MB.

How to Test Your Program

The grader.cpp in the problem directory is a reference implementation of the interaction library. The interaction library used for final testing differs from this reference implementation, so the contestant's solution should not depend on the implementation details of the interaction library.

1. You need to compile the executable program in the problem directory using the following command:
   • g++ grader.cpp sample.cpp -o sample -O2 -lm
2. For the compiled executable:
   • The executable will read data from standard input in the following format:
     • The first line contains two integers $k, m$.
     • The next line contains $k$ integers, where the $i$-th number represents $sgn_i$.
   • After reading, the interaction library will call the function solve exactly once. After your function returns correctly, the interaction library will determine if your calculation is correct. If correct, it will output Correct and information about the number of interaction function calls; otherwise, it will output the corresponding error message.

There is a reference code sample.cpp provided by the problem setter in the problem directory. Note that this code is not guaranteed to pass all test cases.

Examples

Input 1

8192 8200
(sgn values)

Output 1

Correct

Input 2

8192 5550
(sgn values)

Output 2

Correct

Constraints

Scoring

For any data in a subtask, if the contestant returns an incorrect answer or exceeds the query limit, the score is $0$.

Otherwise, assuming the maximum number of queries across all test cases in a subtask is $a$, the score for each subtask is:

• Subtask 1: $10$
• Subtask 2: $15$
• Subtask 3: $\min \{75, \frac{13800}{\max\{a, 1\}} \}$

In other words, Subtask 3 can receive full marks if and only if $a \le 184$.

The contestant's score for this problem is the sum of the scores of the three subtasks.