Teemu has ten enterprise scale applications due tomorrow. The worst part is that he has not even begun writing them! In other words he is horribly out of time.

Luckily the Lord of Time has noticed Teemu's struggles and has given him the following offer:

I have n clocks on the wall, each with only one hand. Each clock has numbers 1, 2, \ldots, x_i on its face. The state of the clock is the number its hand points to. The state of a clock can only be changed by moving its hand one step either clockwise or counter-clockwise. Note that after the state x_i comes 1.

All the clocks on the wall form a super clock, whose state is the combined state of all clocks. The state of the super clock can only be changed by changing the state of exactly one clock on the wall at a time. If you can create a sequence of state changes so that the super clock reaches all of its states exactly once and returns back to initial state, I'll give you all the time you need to program all the applications.

Teemu needs your help to convince the Lord of Time so that he can finish all of his homework in time.

Input

The first line contains a single integer, n, the number of clocks.

The next line contains n integers, x_1, x_2 \ldots, x_n, the number of different states on i^{th} clock.

Output

Output exactly \prod{x_i} lines, that is, the number of moves necessary to reach all combinations of all clock hand positions.

Each line consists of two integers, i and z, the clock to move and the way it is moved. z = 1 means that i^{th} clock is turned clockwise. x = -1 means that i^{th} clock is turned counter-clockwise.

Limits

• 1 \le n
• 1 \le \prod{x_i} \le 10^5

Example

Input:

2
3 2

Output:

1 1
1 1
2 1
1 -1
1 -1
2 -1

Original: http://www.lookingforachallengethebook.com/