CF896B.Ithea Plays With Chtholly

This is an interactive problem. Refer to the Interaction section below for better understanding.

Ithea and Chtholly want to play a game in order to determine who can use the kitchen tonight.

Initially, Ithea puts n clear sheets of paper in a line. They are numbered from 1 to n from left to right.

This game will go on for m rounds. In each round, Ithea will give Chtholly an integer between 1 and c, and Chtholly needs to choose one of the sheets to write down this number (if there is already a number before, she will erase the original one and replace it with the new one).

Chtholly wins if, at any time, all the sheets are filled with a number and the n numbers are in non-decreasing order looking from left to right from sheet 1 to sheet n, and if after m rounds she still doesn't win, she loses the game.

Chtholly really wants to win the game as she wants to cook something for Willem. But she doesn't know how to win the game. So Chtholly finds you, and your task is to write a program to receive numbers that Ithea gives Chtholly and help her make the decision on which sheet of paper write this number.

这是一个交互式问题。请参阅下方的“交互说明”部分以更好地理解。

Ithea 和 Chtholly 想通过一个游戏来决定今晚谁可以使用厨房。

初始时，Ithea 将 $n$ 张空白纸片从左到右排成一行，编号依次为 $1$ 到 $n$。

游戏共进行 $m$ 轮。每轮中，Ithea 会给 Chtholly 一个介于 $1$ 到 $c$ 之间的整数，Chtholly 需要选择其中一张纸片写下该数字（若该纸片上已有数字，则擦除原有数字并用新数字替换）。

若在任意时刻，所有纸片均已被填入数字，且从左至右（即从第 $1$ 张纸片到第 $n$ 张纸片）所写的 $n$ 个数字构成一个非递减序列，则 Chtholly 获胜；若经过全部 $m$ 轮后她仍未获胜，则她输掉游戏。

Chtholly 非常想赢得这场游戏，因为她想为 Willem 做点好吃的。但她不知道该如何获胜。因此，Chtholly 找到了你，而你的任务是编写一个程序：接收 Ithea 提供给 Chtholly 的数字，并帮助她决定将该数字写在哪一张纸片上。

The first line contains 3 integers n, m and c (, means rounded up) — the number of sheets, the number of rounds and the largest possible number Ithea can give to Chtholly respectively. The remaining parts of input are given throughout the interaction process.

第一行包含三个整数 $n$、$m$ 和 $c$（， 表示对 向上取整），分别表示纸张数量、轮数以及 Ithea 能给予 Chtholly 的最大可能数值。输入的其余部分将在交互过程中给出。

In the example, Chtholly initially knew there were 2 sheets, 4 rounds and each number was between 1 and 4. She then received a 2 and decided to write it in the 1st sheet. Then she received a 1 and wrote it in the 2nd sheet. At last, she received a 3 and replaced 1 with 3 in the 2nd sheet. At this time all the sheets were filled with a number and they were non-decreasing, so she won the game.

Note that it is required that your program terminate immediately after Chtholly wins and do not read numbers from the input for the remaining rounds. If not, undefined behaviour may arise and it won't be sure whether your program will be accepted or rejected. Also because of this, please be careful when hacking others' codes. In the sample, Chtholly won the game after the 3rd round, so it is required that your program doesn't read the number of the remaining 4th round.

The input format for hacking:

• The first line contains 3 integers n, m and c;
• The following m lines each contains an integer between 1 and c, indicating the number given to Chtholly in each round.

在示例中，Chtholly 最初知道共有 2 张纸、4 轮游戏，且每个数字均在 1 到 4 之间。随后她收到数字 2，并决定将其写在第 1 张纸上；接着她收到数字 1，并将其写在第 2 张纸上；最后她收到数字 3，并将第 2 张纸上的 1 替换为 3。此时所有纸张均已填入数字，且这些数字构成非递减序列，因此她赢得了游戏。

注意：你的程序必须在 Chtholly 获胜后立即终止，不得再从输入中读取剩余轮次的数字。否则将导致未定义行为，且无法保证你的程序会被接受或拒绝。同样出于这一原因，请在对他人代码进行 hack 时务必谨慎。在本样例中，Chtholly 在第 3 轮后即获胜，因此你的程序不得读取第 4 轮（即剩余轮次）的数字。

用于 hack 的输入格式如下：

• 第一行包含三个整数 $n$、$m$ 和 $c$；
• 接下来的 $m$ 行每行包含一个介于 1 到 $c$ 之间的整数，表示每轮提供给 Chtholly 的数字。