#P1770H. Koxia, Mahiru and Winter Festival

Koxia, Mahiru and Winter Festival

Description

Wow, what a big face!
Kagura Mahiru

Koxia and Mahiru are enjoying the Winter Festival. The streets of the Winter Festival can be represented as a n×nn \times n undirected grid graph. Formally, the set of vertices is {(i,j)    1i,jn}\{(i,j) \; | \; 1 \leq i,j\leq n \} and two vertices (i1,j1)(i_1,j_1) and (i2,j2)(i_2,j_2) are connected by an edge if and only if i1i2+j1j2=1|i_1-i_2|+|j_1-j_2|=1.

A network with size n=3n = 3.

Koxia and Mahiru are planning to visit The Winter Festival by traversing 2n2n routes. Although routes are not planned yet, the endpoints of the routes are already planned as follows:

  • In the ii-th route, they want to start from vertex (1,i)(1, i) and end at vertex (n,pi)(n, p_i), where pp is a permutation of length nn.
  • In the (i+n)(i+n)-th route, they want to start from vertex (i,1)(i, 1) and end at vertex (qi,n)(q_i, n), where qq is a permutation of length nn.
A network with size n=3n = 3, points to be connected are shown in the same color for p=[3,2,1]p = [3, 2, 1] and q=[3,1,2]q = [3, 1, 2].

Your task is to find a routing scheme — 2n2n paths where each path connects the specified endpoints. Let's define the congestion of an edge as the number of times it is used (both directions combined) in the routing scheme. In order to ensure that Koxia and Mahiru won't get too bored because of traversing repeated edges, please find a routing scheme that minimizes the maximum congestion among all edges.

An example solution — the maximum congestion is 22, which is optimal in this case.

The first line contains an integer nn (2n2002 \leq n \leq 200) — the size of the network.

The second line contains nn integers p1,p2,,pnp_1, p_2, \dots, p_n (1pin1 \leq p_i \leq n).

The third line contains nn integers q1,q2,,qnq_1, q_2, \dots, q_n (1qin1 \leq q_i \leq n).

It is guaranteed that both pp and qq are permutations of length nn.

Output 2n2n lines, each line describing a route.

The first nn lines should describe the connections from top to bottom. The ii-th line should describe the route starting at vertex (1,i)(1, i) and ending at vertex (n,pi)(n, p_i).

The next nn lines should describe the connections from left to right. The (i+n)(i+n)-th line should describe the route starting at vertex (i,1)(i, 1) and ending at vertex (qi,n)(q_i, n).

Each line describing a route should start with an integer kk (2k1052 \le k \le 10^5) — the number of vertices the route passes, including the starting and ending vertices. Then output all the vertices on the route in order. In other words, if the route is (x1,y1)(x2,y2)(xk,yk)(x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k), then output k x1 y1 x2 y2xk ykk~x_1~y_1~x_2~y_2 \ldots x_k~y_k. Note that xixi+1+yiyi+1=1|x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 should holds for 1i<k1 \le i < k.

If there are multiple solutions that minimize the maximum congestion, you may output any.

Input

The first line contains an integer nn (2n2002 \leq n \leq 200) — the size of the network.

The second line contains nn integers p1,p2,,pnp_1, p_2, \dots, p_n (1pin1 \leq p_i \leq n).

The third line contains nn integers q1,q2,,qnq_1, q_2, \dots, q_n (1qin1 \leq q_i \leq n).

It is guaranteed that both pp and qq are permutations of length nn.

Output

Output 2n2n lines, each line describing a route.

The first nn lines should describe the connections from top to bottom. The ii-th line should describe the route starting at vertex (1,i)(1, i) and ending at vertex (n,pi)(n, p_i).

The next nn lines should describe the connections from left to right. The (i+n)(i+n)-th line should describe the route starting at vertex (i,1)(i, 1) and ending at vertex (qi,n)(q_i, n).

Each line describing a route should start with an integer kk (2k1052 \le k \le 10^5) — the number of vertices the route passes, including the starting and ending vertices. Then output all the vertices on the route in order. In other words, if the route is (x1,y1)(x2,y2)(xk,yk)(x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k), then output k x1 y1 x2 y2xk ykk~x_1~y_1~x_2~y_2 \ldots x_k~y_k. Note that xixi+1+yiyi+1=1|x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 should holds for 1i<k1 \le i < k.

If there are multiple solutions that minimize the maximum congestion, you may output any.

样例输入 1

3
3 2 1
3 1 2

样例输出 1

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

样例输入 2

4
3 4 2 1
2 4 1 3

样例输出 2

6 1 1 1 2 2 2 2 3 3 3 4 3
6 1 2 1 3 2 3 2 4 3 4 4 4
5 1 3 2 3 2 2 3 2 4 2
7 1 4 1 3 1 2 2 2 2 1 3 1 4 1
7 1 1 2 1 3 1 3 2 3 3 2 3 2 4
6 2 1 2 2 3 2 4 2 4 3 4 4
6 3 1 3 2 3 3 3 4 2 4 1 4
5 4 1 4 2 4 3 3 3 3 4

样例输入 3

3
1 2 3
1 2 3

样例输出 3

3 1 1 2 1 3 1 
3 1 2 2 2 3 2 
3 1 3 2 3 3 3 
3 1 1 1 2 1 3 
3 2 1 2 2 2 3 
3 3 1 3 2 3 3

Note

The first example corresponds to the figures in the problem statement.

The output for examples 22 and 33 respectively are visualized below:

Sample output for examples 22 and 33. Maximum congestions are 22 and 11 respectively.