Description

SNS is going to hold a contest. There are a total of $n$ events, and the contest is held in $n$ rounds, with each event being used in exactly one round.

The principal wants the results to be more diverse, so he decides to find $2^n$ contestants with suitable strength from the students, such that in every event, everyone’s strength is pairwise different.

After selecting all contestants, the principal then makes a suitable schedule of rounds. In each round, for the corresponding event, the stronger half of the contestants advance, and the rest are eliminated and do not participate in later rounds, until only one contestant remains as the final champion.

The principal hopes that, among all different schedules of the $n$ rounds, the number of different people who could possibly become the champion is as large as possible. Now he wants to compute this maximum value, and for each contestant who can possibly become the champion, find one ordering of the events (i.e. a schedule of rounds) that makes them the champion.

Because the principal is busy, he asks you, the first AKIOIer in the school, to help him finish this task. Specifically, you need to first provide, for $i = 1, 2, \dots, n$, the ranking of contestants’ strength from strongest to weakest in event $i$ (represented by a permutation of contestant IDs). Then, for each contestant who can possibly become the champion, you need to provide a permutation of $1, 2, \dots, n$ representing an ordering of rounds that makes them the champion. See the Output Format.

Input Format

One line containing a positive integer $n$.

Output Format

Output one number $m$ on the first line, meaning the maximum number of people who can possibly become the champion.

In the next $n$ lines, on line $i$, output $2^n$ numbers in order, representing the contestant IDs ranked from strongest to weakest in event $i$.

In the next $m$ lines, each line first outputs a number $x$ representing the ID of a contestant who can become the champion, then outputs a permutation of $1, 2, \dots, n$ representing one scheduling method that makes $x$ become the champion.

Please make sure the output format is correct, otherwise the Special Judge may produce errors.

2

2
1 3 2 4
3 1 4 2
1 2 1
3 1 2

Hint

Sample Explanation

First, since there are at most $2$ different scheduling methods, it is clear that at most $2$ people can possibly become the champion.

For contestant $1$, event $2$ first eliminates $4, 2$, leaving contestants $1, 3$. Then event $1$ eliminates $3$, and finally $1$ becomes the champion.

For contestant $3$, event $1$ first eliminates $2, 4$, leaving contestants $1, 3$. Then event $2$ eliminates $1$, and finally $3$ becomes the champion.

Constraints

This problem has $11$ test points. For test point $i$, it satisfies $n = i + 2$.

The scores of each test point are $6, 7, 8, 8, 8, 8, 8, 11, 11, 12, 13$, respectively.

This problem provides the Special Judge source code and checker.exe (see Attachment Download). The following are possible return results of checker.exe and their meanings:

• Wrong answer.: The number of possible champions $m$ is incorrect.

• Invalid contestant number.: An invalid contestant ID appears, including contestant IDs not being integers in $[1, 2^n]$, or a ranking not being a permutation of $1, 2, \dots, 2^n$.

• Invalid item number.: An invalid event number appears, including event numbers not being integers in $[1, n]$, or a ranking not being a permutation of $1, 2, \dots, n$.

• Contestant didn't won the first prize.: Some contestant cannot become the champion under the schedule you provided.

• Accepted: The answer is correct.

Translated by ChatGPT 5