Today is Dongdong's birthday, and he has invited $N$ friends to a party. Friends know that Dongdong loves jelly the most, so every friend brings a bag of jelly as a birthday gift.

When each friend gives him a bag of jelly, they also provide a lucky number $L$ ($1 \le L \le N$). Dongdong first sets this bag of jelly aside and sorts all previously received bags of jelly by the number of jellies in them in ascending order (if the number of jellies is equal, the relative order is arbitrary). Then, Dongdong inserts the current bag of jelly into the sorted queue of jelly bags so that the queue remains sorted (if there are other jelly bags with the same number of jellies, this bag is placed before them). After completing this operation, Dongdong performs the following:

• If the friend is a boy, Dongdong starts from the bag immediately following the one the friend brought and counts $L$ bags backward (using the friend's lucky number), then takes one jelly from that bag and eats it.
• If the friend is a girl, Dongdong starts from the bag immediately preceding the one the friend brought and counts $L$ bags forward (using the friend's lucky number), then takes one jelly from that bag and eats it.

Dongdong is so careless that after receiving all the gifts, he does not know whose jelly he has eaten. Now, he hopes you can help him. Immediately after he eats a jelly, tell him who might have sent it (since the sorting is not unique, Dongdong only requires you to provide one possible answer).

This is an interactive problem. You must call the library functions to perform all operations and cannot access any files.

Constraints

For all data, we guarantee: $1 \le N \le 500,000$, $0 \le \text{count} \le 10^8$, $1 \le L \le N$.

Examples

Input 1

3
32 1 1
1 1 1
23 1 0

Output 1

-1
1
2