L. Broken trophy
time limit per test
1 second
memory limit per test
16 megabytes
input
standard input
output
standard output

Coming back home after triumphally winning your long-coveted trophy, you discover that it was shattered to pieces in your trunk. It just remains to repair it.

Your trophy had the shape of a rectangle of size $$$3 \times N$$$, for some integer $$$N \geq 1$$$, thereby consisting of 3 lines and $$$N$$$ columns, containing a total of $$$3N$$$ unit squares. It was broken into $$$K$$$ pieces, the $$$k^\text{th}$$$ piece being a rectangle of size $$$A_k ×\times B_k$$$ for some integers $$$A_k$$$ and $$$B_k$$$ such that $$$1 \leq A_k \leq B_k \leq 3$$$. Such pieces may have been rotated, or even flipped, in the havoc that is your trunk.

As the first step towards repairing your trophy, you should reassemble them in the form of a rectangle of size $$$3 \times N$$$. More precisely, you have drawn, on a sheet of paper, a $$$3 \times N$$$ rectangle on which you will place your $$$K$$$ pieces, and you need to know, for all integers $$$i \leq 3$$$ and $$$j \leq N$$$, which piece will cover the unit square on the $$$i^\text{th}$$$ line and $$$j^\text{th}$$$ column of your rectangle.

Input

The input consists of three lines, each one containing space-separated integers. The first line contains the numbers $$$K$$$ and $$$N$$$. The second line contains the numbers $$$A_1, A_2, \dots, A_K$$$. The third line contains the numbers $$$B_1, B_2, \dots, B_K$$$.

Limits

  • $$$1 \leq K \leq 300~000$$$;
  • $$$1 \leq N \leq 100~000$$$;
  • $$$1 \leq A_k \leq B_k \leq 3$$$ for all $$$k \leq K$$$;
  • the pieces described in the input can be reassembled in the form of a rectangle of size $$$3 \times N$$$.
Output

The output should contain three lines, each one consisting of $$$N$$$ space-separated integers. If you plan to cover the unit square on the $$$i^\text{th}$$$ line and $$$j^\text{th}$$$ column with the $$$k^\text{th}$$$ piece, the $$$j^\text{th}$$$ number on the $$$i^\text{th}$$$ output line should be the integer $$$k$$$.

In case there are several ways to reassemble your pieces in the form of a rectangle of size $$$3 \times N$$$, every output representing one of these ways is considered correct.

Example
Input
16 17
1 2 1 1 2 1 2 1 1 1 1 1 2 2 1 1
3 3 1 3 2 3 3 1 1 2 2 3 3 3 1 3
Output
1 2 2 2 12 6 4 13 13 16 16 16 9 10 10 7 7
1 2 2 2 12 6 4 13 13 5 5 14 14 14 11 7 7
1 3 15 8 12 6 4 13 13 5 5 14 14 14 11 7 7
Note

Sample Explanation 1

This output represents the following reassembling:

Another valid reassembling could be: