Given balls numbered from to . Each ball has its own color, which you do not know. There are different colors in total.
You can look at a ball in one query and find out the number of balls of the same color that you have already seen (including this one). You will not know the color of the ball itself with such a query. In total, such a query can be made no more than times.
You need to find an array of elements, where each element — an integer from to such that colors[i]=colors[j] if and only if balls with numbers and of the same color.
The first line contains four integers , , , and (1 \leq k \leq n \leq 10^4) — the number of balls, the number of colors, the maximum number of queries, and the block number, respectively. See the constraints on below.
You can make no more than queries. To make a query, you need to output the number and the number (1 \leq index \leq n) in one line — the position of the ball you want to look at. After that, you need to output the end of line character and perform the 'flush' operation. Only after that can you read the answer.
When you already know the answer — you need to output the number and integers of the array , where each element is from to . After that, you need to output the end of line character, perform the 'flush' operation, and terminate the program.
Example
5 3 100 0
0
0
1
1
0
2
31 1
1 2
1 3
1 4
1 5
1 1
1 3
2 1 2 1 2 3Let n=5, k=3, c=100 and a = [2\ 1\ 2\ 1\ 3].
If you look at a ball , you will get a value of . If you look at the ball again, the value will be . Now, if you look at the ball , the value will be . Then for ball — we get . For ball — we get . For ball — we get .
After that, the array [2\ 3\ 2\ 3\ 1] can be returned. This answer will be correct.
( points) n \le 10^4; k = n-1; c = 5 \cdot 10^4; there are two balls of the same color, and the rest of the balls are of different colors;
( points) n \le 10^4; k = 2; c = 5 \cdot 10^4;
( points) n \le 500; k \le n; c = 3 \cdot 10^5;
( points) n \le 10^4; k \le 10; c = 3 \cdot 10^5;
( points) n \le 10^4; k \le n; c = 2 \cdot 10^4; for each color from to , the number of balls of this color is different; each color occurs at least once;
(up to points) n \le 10^4; k \le n; c = 4 \cdot 10^6:
points if you use no more than 4 \cdot 10^6 requests;
points if you use no more than 10^6 requests;
points if you use no more than 6 \cdot 10^5 requests;
points if you use no more than 3 \cdot 10^5 requests;