Railway Siding

A railway siding has two dead-end sidetracks, numbered $1$ and $2$. Cars enter the siding from track A and leave it on track B.

There are $n$ cars on track A, numbered $1$ to $n$. They enter the siding in the order $a_1, a_2, \dots, a_n$. We want them to leave on track B in the order $1, 2, \dots, n$.

Each car is moved once from track A onto sidetrack $1$ or $2$, and later moved once from that sidetrack onto track B. A sidetrack behaves like a stack: the car placed on it most recently is the first one that can be removed. The sidetracks are long enough to hold any number of cars, so their capacity is never a concern.

Cars leave track A strictly in the order $a_1, a_2, \dots, a_n$, but you may move a car from a sidetrack to track B at any moment, including between the arrivals of later cars. Decide whether the cars can be reordered into $1, 2, \dots, n$ on track B, and if so, choose which sidetrack each car is placed on.

The first line contains one integer $n$ ($1 \le n \le 1000$), the number of cars.

The second line contains $a_1, a_2, \dots, a_n$, a permutation of $1, 2, \dots, n$, separated by single spaces.

If the cars cannot be rearranged into the order $1, 2, \dots, n$ on track B, print a single line containing the word NIE (meaning it is impossible).

Otherwise, print TAK (meaning it is possible) on the first line. On the second line print $n$ integers separated by single spaces: the $i$-th integer is the sidetrack ($1$ or $2$) onto which car $a_i$ is moved.

If more than one valid assignment exists, print the lexicographically smallest one: compare two assignment sequences position by position from left to right, and prefer the one with the smaller sidetrack number at the first position where they differ.

Take the sequence $a = [1, 3, 4, 2]$. Move car $1$ onto sidetrack $1$ and immediately move it to track B. Move car $3$ onto sidetrack $1$, then car $4$ onto sidetrack $2$. Finally move car $2$ onto sidetrack $1$; now cars $2$ and then $3$ leave sidetrack $1$ onto track B, followed by car $4$ from sidetrack $2$. Track B receives $1, 2, 3, 4$ in order, and the sidetrack choices are $1\ 1\ 2\ 1$.