2080 - [Poi2010]Railway

一个铁路包含两个侧线1和2，右边由A进入，左边由B出去（看下面的图片）

有n个车厢在通道A上，编号为1到n，它们被安排按照要求的顺序（a1,a2,a3,a4....an）进入侧线，进去还要出来，它们要按照编号顺序（1，2，3，4，5。。。。n）从通道B出去。他们从A到1或2，然后经过一系列转移从B出去，不用考虑容量问题。

输入

输入：第一行一个整数n（1<=n<=100000）表示要转移的车厢总数，第二行为进入侧线的要求顺序a1.a2.a3.a4....an，由空格隔开。

输出

输出：如果可以按照编号顺序到通道B，则输出两行，第一行为TAK，第二行为n个由空格隔开的整数，表示每个车厢进入的侧线编号（1,2）。否则输出NIE。要求输出字典序最小的方案

样例

输入

[样例输入1]
4
1 3 4 2
[样例输入2]
4
2 3 4 1

输出

[样例输出1]
TAK
1 1 2 1 （1号线进到侧线1，然后出来，3号进入侧线1,4号进入侧线2,2号进入侧线1，然后出来，接着3号出来，4号出来）
[样例输出2]
NIE （不可能。。No）
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题