Bajtazar has just bought a balance scale with a set of seven weights with masses of 1, 2, 3, 4, 5, 6, and 7 kilograms. Unfortunately, the weights do not differ in appearance, and none of them have any markings.

The set includes stickers with the numbers 1, 2, 3, 4, 5, 6, and 7, but no instructions on which sticker to place on which weight. For now, Bajtazar has placed the stickers as he saw fit (one sticker per weight), but ultimately he would like each sticker to represent the actual mass of the weight.

Bajtazar has come up with a brilliant idea on how to do this. He can place some weights on the scale pans and observe which way the scale tips. Will you help Bajtazar determine the correct assignment of stickers to weights using a small number of weighings?

Interaction

You must implement a program that solves Bajtazar's problem using the provided library (which simulates the scale). To use the library, include the following in your program:

• C/C++: #include "waglib.h"
• Python: from waglib import liczba_testow, poloz_lewo, poloz_prawo, odloz, wazenie, odpowiedz

The library provides the following functions:

• liczba_testow() – During a single execution of the program, you will need to help Bajtazar multiple times (for different sets of weights). This function returns an integer $t$, representing the number of test cases to consider in the given run. You may assume that in the sample test $t = 2$, and in the remaining tests $t = 5040$.
• poloz_lewo(x) – Places the weight with sticker $x$ ($1 \le x \le 7$) on the left scale pan.
• poloz_prawo(x) – Places the weight with sticker $x$ ($1 \le x \le 7$) on the right scale pan.
• odloz(x) – Places the weight with sticker $x$ ($1 \le x \le 7$) on the table (i.e., removes it from the scale pans). The functions poloz_lewo, poloz_prawo, and odloz can be called regardless of the weight's position before the call. If the weight was already in the position you are trying to set, the function call has no effect.
• wazenie() – Returns a number from the set $\{-1, 0, 1\}$, representing: left pan heavier, scale in balance, right pan heavier, respectively.
• odpowiedz(T) – This function allows you to submit the solution to Bajtazar's problem. It must be called exactly once for each test case. It takes an array $T[0..6]$ (provided as std::vector<int> in C/C++ or a list in Python), which means that the weight on which Bajtazar temporarily placed the sticker with number $i$ weighs $T[i-1]$. After calling the odpowiedz function, the program automatically proceeds to the next test case (in particular, all weights that were on the scale are removed). After executing this function on the last test, the program will automatically terminate.

The library does not have to assign stickers to weights at the beginning of the interaction with your program. It may change the weights of the weights during the interaction, as long as the new weights are still consistent with the results returned by previous calls to the wazenie function.

Your program must not open any files or use standard input and output. The solution will be compiled with the library using the following commands:

• C++: g++ -O3 -static waglib.cpp wag.cpp
• Python: python3 wag.py

Subtasks

Your program will be tested on one group of tests.

If $R$ is the maximum number of calls to the wazenie function that your program performed in a single test case, your solution will receive the following number of points:

Example program execution

Below is the execution of the program for the sample test, in which there are $t = 2$ test cases. Let $w_i$ denote the mass of the weight on which Bajtazar placed the sticker with number $i$.

In the first case, the stickers are placed correctly ($w_i = i$ for each $i$), and we manage to verify this using three calls to the wazenie function.

In the second case, we have $w_1 = 2, w_2 = 1, w_3 = 3, w_4 = 7, w_5 = 4, w_6 = 5$ and $w_7 = 6$. If we also use at most 9 calls to the wazenie function in this case, we will receive 100 points for this test.

Experiments

Example incorrect solutions along with example libraries can be found in the dlazaw folder. The libraries may differ in behavior from those on the testing system and may not meet the problem's assumptions. They are only intended to show how to interact with the program.