This is a communication problem.

Flower, Huahua, and Qingyu are close friends who will form a team to participate in the Pb Olympiad in Informatics hosted by country P.

In this competition, the three-person team needs to solve the following problem:

• Flower and Huahua each hold $N$ binary strings of length exactly $L$.
  • Flower holds the strings $A_0, A_1, \dots, A_{N-1}$, and Huahua holds the strings $B_0, B_1, \dots, B_{N-1}$.
• The judge then selects $Q$ pairs $(x_i, y_i)$ such that $0 \le x_i, y_i < N$. Note that it is possible that $x_i = y_i$.
• For each $0 \le i < Q$, a binary string $C_i$ of length exactly $L$ is generated such that for any $0 \le j < N$, $C_i[j] = A_{x_i}[j] \oplus B_{y_i}[j]$, where $\oplus$ denotes the bitwise XOR operation.
• The judge sends all $Q$ strings $C_0, C_1, \dots, C_{Q-1}$ to Qingyu, but Qingyu has no information about $A$ or $B$.
• Qingyu's task is to find $Q$ pairs $(x'_i, y'_i)$ such that for any $0 \le i < Q$ and $0 \le j < N$, $C_i[j] = A_{x'_i}[j] \oplus B_{y'_i}[j]$.

Obviously, this task is too difficult for Qingyu. Fortunately, Flower and Huahua have superpowers and can send secret messages to Qingyu in one direction. Specifically, Flower and Huahua can each send a binary string of length exactly $M=6\,000$ to Qingyu as hints. Unfortunately, Qingyu does not possess the same ability and can only receive information one-way, without being able to ask them questions.

The team's score depends on the accuracy $P$ of Qingyu's answers. When $P \geq 99\%$, the team receives full marks.

Now, they need your help to design a strategy for each person to achieve their goal.

Formal Problem Statement

Two programs, Flower and Huahua, each have $N$ binary numbers of length $L$ ($A_{0\dots N-1}$ and $B_{0\dots N-1}$, which may have leading zeros). They can each send some information to a third program, Qingyu. The third program needs to answer $Q$ queries, where each query requires finding two indices $i, j$ such that $A_i \oplus B_j$ is exactly the given binary string. It is guaranteed that at least one valid solution exists.

Implementation Details

This is a communication problem; only the C++ language is supported.

You need to submit three programs: Flower, which describes Flower's strategy for sending information to Qingyu; Huahua, which describes Huahua's strategy for sending information to Qingyu; and Qingyu, which describes Qingyu's strategy for answering the questions after receiving the information from the judge, Flower, and Huahua.

Flower

The first program you submit is Flower, which describes Flower's strategy for sending information to Qingyu.

You must include the header Flower.h and implement the following function:

std::string FlowerMessage(int T, int N, int L, std::vector<std::string> A);

• In each test case, this function will be called exactly once.
• The parameter T represents the current subtask number.
• The parameter N is the $N$ from the problem description.
• The parameter L is the $L$ from the problem description.
• The parameter A is an array of length $N$, where A[i] ($0 \le i < N$) is a string of length exactly $L$ describing $A_i$.
• You must return a string $S_F$ of length exactly $M = 6\,000$ consisting only of 0 and 1, describing the information Flower sends.

Huahua

The second program you submit is Huahua, which describes Huahua's strategy for sending information to Qingyu.

You must include the header Huahua.h and implement the following function:

std::string HuahuaMessage(int T, int N, int L, std::vector <std::string> B);

• In each test case, this function will be called exactly once.
• The parameter T represents the current subtask number.
• The parameter N is the $N$ from the problem description.
• The parameter L is the $L$ from the problem description.
• The parameter B is an array of length $N$, where B[i] ($0 \le i < N$) is a string of length exactly $L$ describing $B_i$.
• You must return a string $S_H$ of length exactly $M = 6\,000$ consisting only of 0 and 1, describing the information Huahua sends.

Qingyu

The third program you submit is Qingyu, which describes Qingyu's strategy for answering the questions.

You must include the header Qingyu.h and implement the following function:

std::vector <std::pair <int, int> > Solve(int T, int N, int L, int Q, std::vector <std::string> C, std::string SF, std::string SH);

• In each test case, this function will be called exactly once.
• The parameter T represents the current subtask number.
• The parameter N is the $N$ from the problem description.
• The parameter L is the $L$ from the problem description.
• The parameter Q is the $Q$ from the problem description.
• The parameter C is an array of length $Q$, where C[i] ($0 \le i < Q$) is a string of length exactly $L$ describing $C_i$.
• The parameter SF is a string of length exactly $M = 6\,000$ consisting only of 0 and 1, describing the information Flower sent.
• The parameter SH is a string of length exactly $M = 6\,000$ consisting only of 0 and 1, describing the information Huahua sent.
• You must return an array of length exactly $Q = 500$ consisting of pairs $(x', y')$. The $i$-th ($0 \le i < Q$) pair describes the values of $x'_{i+1}, y'_{i+1}$.
  • For a given query, if there are multiple valid pairs, you may output any one of them.
  • The input data guarantees that at least one valid pair $(x', y')$ exists.

Examples

Input 1

(input data)

Output 1

(output data)

Subtasks

Please note that the total score for this problem is 50 points.

For all data except the samples, $Q = 500$. The ranges for $N$ and $L$ are shown in the table:

• Special Property A: It is guaranteed that $A[i]$ and $B[i]$ are generated by choosing each bit uniformly and independently from 0 and 1. There are only 10 test cases in this subtask.

In each test case, let $S$ be the full score. You can obtain partial points based on the accuracy $P$:

That is, to obtain full marks, you must correctly answer at least 495 out of the 500 queries.

Hack

Hack functionality is not available for this problem.