「POI2010」铁路 Railway

题目描述

译自 POI 2010 Stage 1.「Kolej」

一个铁路包含两个侧线 $1$ 和 $2$ ，左边由 $A$ 进入，右边由 $B$ 出去（如下图所示）。

有 $n$ 个车厢在通道 $A$ 上，编号为 $1$ 到 $n$ ，它们按照 $a_1,a_2,\cdots ,a_n$ 的顺序进入侧线，想要按照 $1,2,\cdots ,n$ 的顺序从通道 $B$ 出去。
他们可以从 $A$ 到 $1$ 或 $2$ ，然后经过一系列转移从 $B$ 出去（不用考虑容量问题）。求是否能够做到，如果可以，请找出一种方案。

输入格式

第一行一个正整数 $n$ 。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。

输出格式

第一行一个字符串，如果能够做到，输出 TAK ，否则输出 NIE 。
若能做到，第二行 $n$ 个空格隔开的正整数，表示每个车厢进入的侧线编号。
如果有多解，输出任意一种。

样例 1

样例 1

输入

4
1 3 4 2

输出

TAK
1 1 2 1

样例 2

样例 2

输入

4
2 3 4 1

输出

NIE

数据范围与提示

对于 $100\%$ 的数据，有 $n \le 1 \times 10^5$。

Translated by Diamond_duke