Background

  "As the ice thaws, the flowers bloom in full; the lingering cold leaves only a few blossoms."

  Guitar, bass, keyboard, drums.

  Their voices, the sunlight around seven or eight o'clock.

  Stewed into a corner, the so-called look of youth.

  Sadly, they still have to carry the win and loss

  On shoulders pretending to be mature.

  Vernal Equinox "There is an invisible magnetic field between you and me, chasing until one day we collide, let sparks burst forth."

Problem Description

In the corridor outside the lounge, there is a TV screen. Besides the countdown to the College Entrance Examination, it sometimes shows some boring stuff. During a break in practice, Tianyi rests on Ayaka's legs and listens carefully, and then hears—

Now there is a foreign guy who has made a bulky, flashy, and useless galvanic cell device. Tianyi imagines it as follows:

We only care about the red part in the middle. They are several partition plates used to separate the solutions on the left and right. These partition plates can be removed, can be assembled together in any order into any set, and can be flipped left-to-right.

Now the guy has two sets of solutions. The first set is $X=\{x_1,x_2,\cdots,x_n\}$, and the second set is $Y=\{y_1,y_2,\cdots,y_n\}$. These $2n$ solutions are pairwise different. The guy wants to place each solution in set $X$ on the left side of the container and each solution in set $Y$ on the right side, performing a total of $n^2$ galvanic cell experiments. After each experiment, the rigorous guy will wash the device, but he does not want to wash the partition plates.

During an experiment, if one side of a partition plate directly contacts an experimental solution, then that solution will stick to the corresponding side of the partition plate. To prevent contamination, for any partition plate, any side that has been stained by some solution must not contact an experimental solution of a different type. For example, in the following figure (red vertical lines represent partition plates; blue labels represent solutions already stained on the two sides; black labels represent the solutions used in the current experiment; the same below):

In addition, if multiple partition plates are used at once, since the plates fit tightly, if one side of a plate contacts a side of another plate that has been stained by some solution, then that solution will remain on the contacting sides of both plates. For example, in the following figure (green labels represent solutions newly stained on the two plates after this experiment):

The guy says he hopes to complete all experiments using a small (not necessarily the minimum) number of partition plates, and invites the audience to provide the number of plates $m$ and, for the $n^2$ experiments conducted in order, the types of solutions used on the left and right sides and the plan for using the partition plates.

Tianyi expects the answers in the comments to be unreliable, so she invites you to construct an excellent plan.

Input Format

One line contains an integer $n$, representing the size of sets $X$ and $Y$.

Output Format

Output $n^2+1$ lines describing your construction.

The first line contains an integer $m$, representing the number of partition plates needed. You should guarantee $1\le m\le 712$. For convenience, denote the plates as $C_1,C_2,\cdots,C_m$.

The next $n^2$ lines describe the $i$-th experiment in order, i.e., line $i$ corresponds to the $i$-th experiment:

1. First output an integer $k\in[1,m]$, representing the number of partition plates installed in this experiment.

2. Next output an integer $u\in[1,n]$, indicating that the solution used on the left side is $x_u$.

3. Then output $k$ integers $p_1,p_2,\cdots,p_k$ in order. The $t$-th integer $p_t\in[-m,0)\cup(0,m]$ describes the $t$-th partition plate from left to right:

   • If $p_t>0$, then it is $C_{p_t}$.

   • Otherwise, if $p_t<0$, it means to flip the left and right faces of $C_{-p_t}$ and then install it. Note that after this experiment ends, the default left and right faces of $C_{-p_t}$ are still the faces before flipping. (That is, the effect of flipping will not persist.)

4. Finally output an integer $v\in[1,n]$, indicating that the solution used on the right side is $y_v$.

Multiple integers on the same line must be separated by a single ASCII space, and no extra spaces are allowed at the end of a line. An output that does not follow the format may be judged as Wrong Answer.

2

2
2 1 1 2 1
1 1 1 2
1 2 2 1
2 2 2 1 2

Hint

Sample #1 Explanation

It can be proven that this is a plan with the minimum $m$ when $n=2$.

Constraints

This problem uses Subtask scoring.

For $100\%$ of the testdata, $1\le n\le609$.

For different subtasks, the constraints are as follows:

• Hint 1: Emphasize again that your construction must guarantee $1\le m\le712$.

• Hint 2: For any subtask, it is guaranteed that the output size of the official solution for that subtask does not exceed $5\times10^6$ integers.

Translated by ChatGPT 5