D. DJ Sandália's Electric Trio
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Every February, the streets of Salvador surrender to the Carnaval, and no one feels it more than DJ Sandália, the legendary selector who rides the oldest trio elétrico circling the Campo Grande circuit. The folião crowd shouts song requests all night long, and DJ Sandália has carefully written down, for each of the $$$N$$$ songs in the repertoire, an integer "weight" $$$P_i$$$ that measures how badly the crowd wants to hear song $$$i$$$.

To keep the party fair, DJ Sandália wants to pick the next song at random so that song $$$i$$$ is chosen with probability exactly $$$P_i / (P_1 + P_2 + \dots + P_N)$$$.

There is just one problem: the trio's randomizer is a battered piece of hardware from the 1980s, and the only thing it knows how to do is to draw an integer uniformly at random from a given range. It cannot weight anything by itself; every draw it produces is perfectly uniform.

Working only with this uniform randomizer, DJ Sandália came up with the following strategy. First, choose a single integer $$$K$$$ and build three arrays $$$A$$$, $$$B$$$ and $$$C$$$, each of length $$$N$$$. Then, to pick a song:

  • draw $$$x$$$ uniformly from $$$1$$$ to $$$N$$$;
  • draw $$$y$$$ uniformly from $$$0$$$ to $$$K$$$;
  • if $$$y \lt C_x$$$, play song $$$A_x$$$; otherwise, play song $$$B_x$$$.

Help DJ Sandália choose $$$K$$$ and the arrays $$$A$$$, $$$B$$$ and $$$C$$$ so that this procedure plays song $$$i$$$ with probability exactly $$$P_i / (P_1 + \dots + P_N)$$$, for every song $$$i$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 1000$$$), the number of songs.

The second line contains $$$N$$$ integers $$$P_1, P_2, \dots, P_N$$$ ($$$1 \leq P_i \leq 10^{9}$$$), the weight of each song.

Output

On the first line, print a single integer $$$K$$$ ($$$0 \leq K \leq 10^{18}$$$).

On the second line, print $$$N$$$ integers $$$A_1, \dots, A_N$$$ ($$$1 \leq A_i \leq N$$$).

On the third line, print $$$N$$$ integers $$$B_1, \dots, B_N$$$ ($$$1 \leq B_i \leq N$$$).

On the fourth line, print $$$N$$$ integers $$$C_1, \dots, C_N$$$ ($$$0 \leq C_i \leq K$$$).

Your answer is accepted if, for every song $$$i$$$, the probability that the described procedure plays song $$$i$$$ equals $$$P_i / (P_1 + \dots + P_N)$$$ exactly. Any valid answer will be accepted.

Examples
Input
1
5
Output
4
1
1
4
Input
2
1 3
Output
3
1 2
2 2
2 3
Input
3
1 1 2
Output
3
1 2 3
3 3 3
3 3 3
Note

Explanation for example 1

With a single song, $$$K = 4$$$ and the only bucket points to song $$$1$$$ on both sides, so song $$$1$$$ is always chosen.

Explanation for example 2

Here $$$K = 3$$$. With the printed table, $$$\Pr[1] = \tfrac14 = \tfrac{P_1}{S}$$$ and $$$\Pr[2] = \tfrac34 = \tfrac{P_2}{S}$$$, so it is a valid answer.

Explanation for example 3

Here $$$K = 3$$$. The printed table gives $$$\Pr[1] = \Pr[2] = \tfrac14$$$ and $$$\Pr[3] = \tfrac12$$$, matching $$$P_i / S$$$. Any other valid table is also accepted.