STC07 - Railway

A railroad siding consists of two (dead-end) sidetracks 1 and 2. The siding is entered by track A, and left by track B.

There are N cars on track A, numbered from 1 to N. They are arranged in such a way that they enter the siding in the order a1, a2, a3, ..., aN. The cars are to be transferred to the siding, so that they leave it by track B in the order 1, 2, 3, ..., N. Each car is to be transferred once from track A to one of the sidetracks 1 or 2, and later (possibly after some transfers of the remaining cars) once from that sidetrack to the track B. The sidetracks are long enough to store even the longest trains, so there is no need to worry about their capacity.

Input

The first line of the standard input holds one integer N (1 <= N <= 105) that denotes the number of cars for transfer. The second line stores the numbers a1, a2, a3, ..., aN that are a permutation of 1, 2, 3, ..., N (i.e., each ai belongs to {1, 2, 3, ..., N}, and all these numbers are unique), separated by single spaces.

Output

The first line of the standard output should contain the word TAK (yes in Polish) if there is a way of transferring the cars so that they enter track B in the order 1, 2, 3, ..., N, or the word NIE (no in Polish) if it is impossible. If the answer is TAK, the second line should give, separated by single spaces, the numbers of sidetracks (1 or 2) to which successive cars a1, a2, a3, ..., aN are moved in a correct transfer. If there are several ways of making the transfer, choose lexicographically smallest.

Example

For the input data:

4
1 3 4 2

the correct result is:

TAK
1 1 2 1

And for the input:

4
2 3 4 1

the correct result is:

NIE



Added by:Sergey Kulik
Date:2013-08-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:POI XVII

hide comments
2013-09-24 23:13:37 Mitch Schwartz
@Arivudai Nambi: "The sidetracks are long enough to store even the longest trains, so there is no need to worry about their capacity."
2013-09-24 19:17:10 Arivudai Nambi
Is the first example input correct?
1 3 4 2 to sidings 1 1 2 1.
If 1 goes into siding 1 and gets out; then 3 goes into siding 1 and 4 goes into siding 2 there will be no space for car 2 to go. But it has to be the next one after car 1. You gave output to that as possible. Pls explain.
2013-08-27 23:52:35 Mitch Schwartz
One of the input files is empty (and the expected output file is also empty). Please fix it and rejudge all submissions (checking the box "Refresh cached info about test sequence" if needed)...

reply: rejudged

(Mitch) Thanks.

Last edit: 2013-08-30 14:29:38
2013-08-27 23:12:27 Siarhei Kulik
The test data are official, there is also a solution that gets AC here at SPOJ.
2013-08-26 02:12:40 Mitch Schwartz
@problem setter: Please check the input. My assert on the return value of scanf() failed.

@zukow: Thanks for the picture and the link to the other problem.

Last edit: 2013-08-26 03:01:26
2013-08-25 14:46:48 :D
Also see JZPSTA. It seems to be the exactly same problem, but with more information and constraints on the output.
2013-08-25 14:39:32 :D
Added a picture from official source. I was also not clear on how it should work.
2013-08-18 12:10:30 Mitch Schwartz
@Ramprakash K: I believe it is correct to think of it like STPAR but with two side streets instead of one.
2013-08-18 05:44:05 ramprakash_k
Can you give a pictorial representation of the tracks or explain the test cases please.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.