Champion Tournament Scheduling

In this problem, you are given an integer $n$ and there are $2^n$ players competing in a tournament that is held in $n$ rounds (each round corresponding to a different project). In each project, every player is assigned a distinct strength (ranking) and in every round the top half of the remaining players (according to that project’s ranking) advance, while the rest are eliminated. Before the tournament begins, the principal determines the rankings separately for each of the $n$ projects. In addition, he is allowed to choose the order (a permutation of $\{1,2,\dots,n\}$) in which the projects are held. A player is a potential champion if there exists some choice of the project order (i.e. schedule) so that this player wins every round to become the champion. The principal wishes to design the rankings so that the number of potential champions is as large as possible, and it can be shown that the maximum number is $2^{n-1}$.

Your task is two‐fold:

1. For each project $i=1,2,\dots,n$, output a permutation of $\{1,2,\dots,2^n\}$ representing the ranking order (from strongest to weakest). In other words, the first element in the permutation is the player with the highest strength in project $i$, the second element the next strongest, and so on. You must design these rankings such that the top $2^{n-1}$ players (which we call the potential champions) are always ranked above the remaining players.

2. For each potential champion (players numbered $1, 2, \dots, 2^{n-1}$), output a permutation of $\{1,2,\dots,n\}$ representing a schedule (i.e. the order in which the projects are held) such that when the tournament is simulated the candidate wins every round and becomes champion.

The final output should follow the format below.

Note: All formulas must be written in (\LaTeX) format. The ranking in each project is constructed as follows. Let $k=2^{n-1}$. For each project $i$ (with (1\le i\le n); note that we always have (n\le k) for (n\ge 1)), define the ranking for the potential champions to be a cyclic shift of the identity permutation: [ f_i = [i, i+1, \dots, k, 1,2,\dots,i-1]. ] Then, append the remaining players (from (k+1) to (2^n)) in increasing order.

For each potential champion candidate (x) (with (1\le x\le k)), a valid schedule is given by [ \texttt{schedule}_j = ((x+j)\bmod n)+1, \quad j=0,1,\dots,n-1. ] It can be verified that with these rankings and schedule, if the tournament is simulated as described the candidate will win in every round.

inputFormat

The input consists of a single integer:

n

The integer (n) ((1\le n\le 10) say) is the number of projects (and rounds). There are (2^n) players, numbered from 1 to (2^n).

outputFormat

The output should be formatted as follows:

1. Output (n) lines. The (i)-th line should contain a permutation of ({1,2,\dots,2^n}) representing the ranking order for project (i) (from strongest to weakest). In each ranking the first (2^{n-1}) numbers (potential champions) must appear before all other numbers.

2. Output a line containing the integer (2^{n-1}) — the number of potential champions.

3. Then output (2^{n-1}) additional lines. The (j)-th such line should contain a permutation of ({1,2,\dots,n}) representing a schedule where the corresponding potential champion wins the tournament.

sample

1

1 2
1
1