**Task statistics**

Number of users: 439

Number of users with 100 points: 131

Average result: 35.2574

# Railway

### Memory limit: 128 MB

A railroad siding consists of two (dead-end) sidetracks 1 and 2. The siding is entered by track A, and left by track B (see figure below).

There are cars on track A, numbered from to . They are arranged in such a way that they enter the siding in the order . The cars are to be transferred to the siding, so that they leave it by track B in the order . Each car is to be transferred once from track A to one of the sidetracks 1 or 2, and later (possibly after some transfers of the remaining cars) once from that sidetrack to the track B. The sidetracks are long enough to store even the longest trains, so there is no need to worry about their capacity.

## Input

The first line of the standard input holds one integer () that denotes the number of cars for transfer. The second line stores the numbers that are a permutation of (i.e., each belongs to , and all these numbers are unique), separated by single spaces.

## Output

The first line of the standard output should contain the word `TAK`
(*yes* in Polish) if there is a way of transferring the cars so that they
enter track B in the order , or the word `NIE`
(*no* in Polish) if it is impossible.
If the answer is `TAK`, the second line should give, separated by
single spaces, the numbers of sidetracks (1 or 2) to which successive cars
are moved in a correct transfer.
If there are several ways of making the transfer, choose one arbitrarily.

## Example

For the input data:

4 1 3 4 2

the correct result is:

TAK 1 1 2 1

And for the input:

4 2 3 4 1

the correct result is:

NIE

**Explanation of the example:** In the first example we start by moving
car to the first sidetrack, and move it to track B instantly.
Then the car is moved to the first sidetrack, and car to the other one.
Finally, the car is moved to the first sidetrack, after which the cars
and leave it to enter track B, followed by the car , which enters track
from the second sidetrack.

*Task author: Bartosz Walczak.*