21998번 - BUKA 다국어인터랙티브

문제

City college is in the shape of the complete binary tree with N vertices. Each building corresponds to one of its vertices and each road to one of its edges. The buildings are labeled with numbers 1, ..., N, but the order is not known. The following picture represents college where N is 15 and one of the possible ways to label them.

One warm evening, in the building which corresponds to the root of the trees (node 5 in the picture), a very loud party was beign held. Music could be heard even in the outermost buildings of the college. Also, during the evening many students were walking around the college. Moreover, for each pair of buildings (A, B) there is a student who was walking the shortest route from A to B. We can ask this student where on his path was the music loudest, i.e. what is the building closest to the root which he walked by on his path. Of course, on his way from A to B he can only walk by the edges and the total length of the path is the number of these edges.

For example in the picture above, by walking from bulding 15 to 8 the music was the loudest at building 3, from 6 to 12 at building 5, from 13 and 2 at building 2 and on a route from 10 to 10 of course at building 10.

Your task is to write a program which will by asking at most 50 000 queries described above, determine the building labelling of the college. It is sufficient to determine the parent of for each building. Exceptionally, we define that the parent of the root is the root itself.

입력

출력

제한

인터랙션

Before asking queries, you must read the number N (1 ≤ N ≤ 10 000), the number of buildings. N will always be in the form of 2^K -1 for K being positive integer.

After reading N you can ask queries in the form 'pitaj A B', for some pair of buildings A and B. After each query it is neccessary to flush the output and then read the label of the building which is the answer to the query.

After determining the configuration of the college, you should output 'kraj' and after that N integers in N lines. The number in the i-th line represents the parent of the building labeled with number i. Finally, you must flush the output one last time.

테스팅

You must first create a file containing the test case that you want to test your solution with.

• In the first line there should be an integer N, the number of buildings.
• Next N lines should contain labels of buildings, sorted by levels (higher levels first), and within each level ordered from left to right.

One example of the input file which corresponds to the labelling in the picture:

15
5
3
2
10
8
14
11
4
15
6
7
1
12
13
9

힌트