P7579 "RdOI R2" Weighing (weigh)

Because rui_er is a conscientious problem setter, this problem is an interactive problem.

To prepare for the physical fitness test, rui_er bought $n$ solid shot puts for practice, but found that during shipping, two balls with obviously lighter mass but similar appearance were mixed in (these two balls have the same mass). It is also known that the sum of the masses of these two balls is greater than that of one normal ball. To avoid affecting the training results, we now need to find these two lighter balls. Since searching manually is too slow, rui_er brings a balance scale, which can place several balls on each side and obtain the comparison of the total masses on the two sides. Please help rui_er find the two lighter balls using no more than $k$ weighings. Here, $k$ is an attribute of each test point. You do not need to and should not read it. --- **Interaction Method** This problem uses I/O interaction. You may choose to perform a weighing operation. In that case, print one line to standard output: `1 p a1 a2 ... ap q b1 b2 ... bq`, meaning that $p$ balls with indices $a_1,a_2,\cdots,a_p$ are placed on the left pan, and $q$ balls with indices $b_1,b_2,\cdots,b_q$ are placed on the right pan. Then flush the buffer, and read from standard input one character among `=`, indicating the mass relationship between the left and right pans. For each such query, you must ensure $1\le p,q\le n$, $p+q\le n$, all $a_i$ and $b_i$ are pairwise distinct, and you may perform at most $k$ such queries. After obtaining the answer, print one line to standard output: `2 x y` to submit the answer, meaning that the balls with indices $x$ and $y$ have smaller mass. You must ensure $1\le x\lt y\le n$ (note that you must output in strictly increasing order), and terminate the program immediately after performing this operation. The interaction library has already fixed the actual situation of the balls at the beginning, and it will not change with your queries.

The first line contains an integer $n$, indicating the number of balls. Here, $k$ is an attribute of each test point. You do not need to and should not read it. The next several lines are as described in [Interaction Method].

Several lines, as described in [Interaction Method].

**Sample Explanation** The results of three queries are $a_1=a_2,a_3\lt a_4,a_5\gt a_6$. Thus, we can determine that the two balls with indices $3,6$ have smaller mass. --- **Constraints** This problem uses partial scoring by test point. Among the $20$ non-HACK test points, the first test point is worth $4$ points, and each of the others is worth $5$ points. The $4$ HACK test points are worth a total of $1$ point. If any test point is not passed, no points are awarded. |Test Point|$n\le$|$k=$|Special Property|Test Point|$n\le$|$k=$|Special Property| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |1|$5$|$50$|None|11|$500$|$50$|None| |2|$10$|$50$|None|12|$500$|$50$|None| |3|$100$|$50$|None|13|$500$|$20$|A| |4|$100$|$50$|None|14|$500$|$20$|B| |5|$500$|$50$|A|15|$500$|$20$|A| |6|$500$|$50$|B|16|$500$|$20$|B| |7|$500$|$50$|A|17|$500$|$20$|None| |8|$500$|$50$|B|18|$500$|$20$|None| |9|$500$|$50$|None|19|$500$|$20$|None| |10|$500$|$50$|None|20|$500$|$20$|None| |ex1|$500$|$12$|B/HACK|ex3|$500$|$13$|HACK| |ex2|$500$|$13$|HACK|ex4|$500$|$14$|HACK| - Special Property A: $n=2^i-1,i\in\left\{4,5,6,7,8\right\}$. - Special Property B: $n=2^i,i\in\left\{4,5,6,7,8\right\}$. - Note: For HACK testdata, $k$ is set according to the actual test point settings. It will block some weird approaches and ensure that the intended solution can pass. For all data, $5\le n\le 500$, $k\in\left\{50,20,14,13,12\right\}$. Translated by ChatGPT 5