8522번 - Hyperclock 다국어

Brainy Smurf concluded that days were too short, and, because of that, he would not manage to write all the volumes of Quotations of Brainy Smurf. He decided to visit Father Time and ask him to extend each day to 48 hours. Father Time didn't want to accept his request, but, after Brainy Smurf's importunate demands, eventually agreed. However, he imposed a condition: Brainy Smurf must first solve the Hyperclock puzzle.

The Hyperclock consists of N clocks. Each clock has one hand and some numbers on its face. On the face of i-th clock (1 ≤ i ≤ N) there are numbers from 1 to k_i. At the very beginning, all hands point to the number 1. The puzzle was explained by Father Time as follows:

You have to perform a sequence of moves. In one move you can turn the hand of an arbitrary clock one position clockwise or counterclockwise. After the last move, the Hyperclock's hands must return to their initial positions. Moreover, each possible configuration of the Hyperclock must appear exactly once.

Brainy Smurf has been tinkering with the Hyperclock for over an hour and is becoming increasingly convinced that, despite his wisdom, he will not manage to solve the puzzle. Help him!

The first row of the input contains one positive integer N. In each of the following N rows there is one integer greater than 1: in the (i+1)-th row there is the number k_i. The number of all possible configurations (namely k₁k₂…k_N) is not greater than 10⁶.

If there is no solution for the puzzle, output the single word NIE (Polish for no). Otherwise, k₁k₂…k_N rows should be output, describing the subsequent moves. Each row must contain two integers. The first number i (1 ≤ i ≤ N) is the number of the clock whose hand is turned. The second number indicates a direction: 1 (for clockwise) or -1 (for counterclockwise). If there are many possible solutions, you can output any of them.