철도 대피선

철도 대피선에는 막다른 곁선 두 개가 있으며, 각각 $1$번과 $2$번으로 번호가 매겨져 있습니다. 차량은 A선을 통해 대피선으로 들어오고 B선을 통해 빠져나갑니다.

A선에는 $1$번부터 $n$번까지 번호가 붙은 차량 $n$대가 있습니다. 이 차량들은 $a_1, a_2, \dots, a_n$의 순서로 대피선에 들어옵니다. 우리는 이 차량들이 B선으로 $1, 2, \dots, n$의 순서로 빠져나가게 하려고 합니다.

각 차량은 A선에서 곁선 $1$번 또는 $2$번으로 한 번 옮겨지고, 이후 그 곁선에서 B선으로 다시 한 번 옮겨집니다. 곁선은 스택처럼 동작합니다. 즉, 가장 나중에 올려놓은 차량을 가장 먼저 빼낼 수 있습니다. 곁선은 아무리 긴 열차라도 담을 수 있을 만큼 충분히 길기 때문에 용량은 신경 쓰지 않아도 됩니다.

차량은 반드시 $a_1, a_2, \dots, a_n$의 순서대로 A선을 떠나지만, 곁선에 있는 차량은 언제든지(뒤에 오는 차량이 들어오기 전이라도) B선으로 옮길 수 있습니다. 차량들을 B선에서 $1, 2, \dots, n$의 순서로 정렬할 수 있는지 판단하고, 가능하다면 각 차량을 어느 곁선에 올려놓을지 정하세요.

첫째 줄에 차량의 수를 나타내는 정수 $n$ ($1 \le n \le 1000$)이 주어집니다.

둘째 줄에 $1, 2, \dots, n$의 순열인 $a_1, a_2, \dots, a_n$이 공백 하나로 구분되어 주어집니다.

차량들을 B선에서 $1, 2, \dots, n$의 순서로 정렬할 수 없다면, 불가능함을 뜻하는 단어 NIE를 한 줄에 출력합니다.

정렬할 수 있다면 첫째 줄에 가능함을 뜻하는 TAK를 출력합니다. 둘째 줄에는 공백 하나로 구분된 정수 $n$개를 출력하는데, $i$번째 정수는 차량 $a_i$를 올려놓는 곁선의 번호($1$ 또는 $2$)입니다.

올바른 배치가 여러 가지라면 사전순으로 가장 작은 것을 출력합니다. 두 배치 수열을 왼쪽에서 오른쪽으로 위치별로 비교하여, 처음으로 달라지는 위치에서 곁선 번호가 더 작은 쪽을 택합니다.

수열 $a = [1, 3, 4, 2]$를 생각해 봅시다. 차량 $1$을 곁선 $1$번에 올린 뒤 곧바로 B선으로 옮깁니다. 차량 $3$을 곁선 $1$번에, 차량 $4$를 곁선 $2$번에 올립니다. 마지막으로 차량 $2$를 곁선 $1$번에 올리면, 곁선 $1$번에서 차량 $2$, 그다음 $3$이 B선으로 나가고, 이어서 곁선 $2$번에서 차량 $4$가 나갑니다. B선은 $1, 2, 3, 4$를 순서대로 받으며, 곁선 선택은 $1\ 1\ 2\ 1$입니다.