#733. [Poi2010]Railway

[Poi2010]Railway

Description

一个铁路包含两个侧线1和2,右边由A进入,左边由B出去(看下面的图片) image 有n个车厢在通道A上,编号为1到n,它们被安排按照要求的顺序(a1,a2,a3,a4....an)进入侧线,进去还要出来,它们要按照编号顺序(1,2,3,4,5。。。。n)从通道B出去。他们从A到1或2,然后经过一系列转移从B出去,不用考虑容量问题。

Format

Input

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

Output

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

Samples

4
1 3 4 2
4
2 3 4 1
TAK
1 1 2 1 (1号线进到侧线1,然后出来,3号进入侧线1,4号进入侧线2,2号进入侧线1,然后出来,接着3号出来,4号出来)
NIE (不可能。。No)