This is a communication problem.

Alice manages a beautiful garden with $n$ halls for dining and resting, numbered from $1$ to $n$. These halls are connected by flower corridors, allowing visitors to enjoy the flowers and travel between the halls. Each corridor is planted with flowers of one of three different colors. To ensure orderly visits, for any two distinct halls $u, v$ ($1 \le u < v \le n$), there is exactly one unidirectional corridor connecting $u$ and $v$, meaning the direction of the corridor is either $u \to v$ or $v \to u$.

When visiting the garden, a tourist chooses a sequence of distinct halls and travels in a cycle. Specifically, the tourist chooses $l$ ($l \ge 3$) halls $a_1, \dots, a_l$ and visits the corridors in the order $a_1 \to a_2 \to \dots \to a_l \to a_1$. Due to the directional constraints of the corridors, there are few feasible tour paths. We define $a_1, \dots, a_l$ as a tour path if and only if $l \ge 3$, $a_1, \dots, a_l$ are distinct, and for all $1 \le i \le l$, the corridor connecting $a_i$ and $a_{(i \bmod l)+1}$ is directed as $a_i \to a_{(i \bmod l)+1}$. Two tour paths $a_1, \dots, a_l$ and $b_1, \dots, b_l$ are essentially different if and only if the corridors traversed are different, or the paths are different, i.e., $l_1 \neq l_2$ or for any $0 \le x < l_1$, there exists $0 \le y < l_1$ such that $a_y \neq b_{(y+x-1) \bmod l_1+1}$.

For a tour path, the tourist will see flowers of different colors. If the corridors traversed in the tour path include all three colors, the tourist is satisfied; otherwise, the tourist is dissatisfied. To ensure a good experience, for each hall, there are at most $k$ essentially different tour paths passing through that hall that would make the tourist dissatisfied.

Bob also wants to manage a garden like Alice's, so he obtained Alice's garden design blueprints and built a garden with $n$ halls. However, Alice lost the design blueprints for the corridors. Bob hopes that the layout and directions of the corridors in his garden are the same as Alice's, and that for each hall, there are at most $k$ essentially different tour paths passing through it that make the tourist dissatisfied. Note: The colors of the flowers planted in the corridors do not need to be exactly the same, as long as the above conditions are met.

To complete the construction as quickly as possible, Alice needs to send as little information as possible to Bob so that Bob can build the corridors according to the requirements. Specifically, Alice can transmit a binary string of length $l$ to Bob, and Bob needs to build the corridors of his garden based on this binary string, i.e., determine the direction and flower color for the corridor between every two halls. You need to help Alice send as little information as possible and help Bob build his garden's corridors using this information.

Implementation Details

You do not need to, and should not, implement the main function. You must ensure that your submitted program includes the header file garden.h by adding the following code at the beginning:

#include "garden.h"

You need to implement the following three functions in your source file:

int init(int n, int k);

• $n, k$ represent the number of halls and the upper limit on the number of tour paths that make the tourist dissatisfied, respectively.
• This function must return a non-negative integer $l$, representing the length of the binary string Alice transmits to Bob. You must ensure $0 \le l \le 1.5 \times 10^5$.
• For each test case, this function will be called exactly once by the interactor when the program first starts.

std::string send_message(int n, int k, std::vector<std::vector<std::pair<bool, int>>> e);

• $n, k$ represent the number of halls and the upper limit on the number of tour paths that make the tourist dissatisfied, respectively.
• For $0 \le i \le n - 2$ and $0 \le j \le n - i - 2$, $e_{i,j}$ represents the direction and flower color of the corridor connecting hall $i+1$ and hall $i+j+2$. Specifically, $e_{i,j}$ is a pair:
  • If the first element of $e_{i,j}$ is true, the direction is $i+1 \to i+j+2$, otherwise it is $i+j+2 \to i+1$.
  • The second element of $e_{i,j}$ is a non-negative integer in $\{0, 1, 2\}$, representing the color of the flowers planted in the corridor.
• This function must return a binary string $s$ of length $l$, representing the information Alice transmits to Bob. You must ensure the length of $s$ is the same as the return value of the init function.
• For each test case, this function will be called exactly 10 times by the interactor when the program first starts, and the variables $n, k$ passed to this function are the same as those passed to the init function.

std::vector<std::vector<std::pair<bool, int>>> build_flower_garden(int n, int k, std::string s);

• $n, k, s$ represent the number of halls, the upper limit on the number of tour paths that make the tourist dissatisfied, and the binary string transmitted by Alice to Bob, respectively.
• This function must return the directions and flower colors of the corridors in the garden built by Bob, using the same representation as the variable $e$ passed to the send_message function. You must ensure:
  • The length of $e$ is $n-1$.
  • For $0 \le i \le n-2$, the length of $e_i$ is $n-i-1$.
  • For $0 \le i \le n-2$ and $0 \le j \le n-i-2$, the second element of $e_{i,j}$ is a non-negative integer in $\{0, 1, 2\}$.
• For each test case, this function will be called exactly 10 times by the interactor when the program runs for the second time. The variables $n, k$ passed to this function are the same as those passed to the init function during the first run, and the string $s$ passed to this function for the $c$-th time ($1 \le c \le 10$) is the same as the return value of the $c$-th call to send_message during the first run.
• You must also ensure:
  • For $1 \le c \le 10$, $0 \le i \le n-2$, and $0 \le j \le n-i-2$, the first element of $e_{i,j}$ passed to the $c$-th send_message call during the first run is the same as the first element of $e_{i,j}$ returned by the $c$-th build_flower_garden call during the second run.
  • The corridors built according to the return value of this function satisfy the condition that for every hall, there are at most $k$ essentially different tour paths passing through it that make the tourist dissatisfied.

Note: In any case, the execution time of the interactor will not exceed 0.2 seconds, and the memory used is fixed and does not exceed 64 MiB.

Constraints

For all test data: $t = 10$, $n = 300$, $0 \le k \le 2$. The directions of all corridors are non-negative integers in $\{0, 1\}$. * The colors of the flowers in all corridors are non-negative integers in $\{0, 1, 2\}$.

Scoring

Note: Participants should not obtain internal information about the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. The final evaluation interactor is different from the sample interactor. This problem is subject to the same restrictions as traditional problems; for example, compilation errors result in 0 points, and runtime errors, time limit exceeded, or memory limit exceeded result in 0 points for the corresponding test case. Participants can only access variables defined in their own program and variables provided by the interactor; attempting to access other address spaces may lead to compilation or runtime errors. If the return value of the init function, the send_message function, or the build_flower_garden function is invalid, the corresponding test case will receive 0 points.

Based on the above conditions: * For each test case, let $B$ be the parameter of the subtask to which the test case belongs, and $l$ be the return value of the init function. The score percentage for the test case is shown in the table below:

• The score for each test case is the product of the score percentage and the score of the subtask to which the test case belongs.