URI Online Judge | 3172

Dali and Dila

By Maycon Alves, Inatel BR Brazil

Timelimit: 1

Dali and Dila are two elf brothers who recently started working in Santa's workshop. For their first task, they were both assigned to move the toys produced in the workshop to the wrapping room using a magic sled.

The toys were separated into N piles, which, by a strange rule of the elves, must always be ordered in a non-decreasing way. The brothers then need to remove the toys from the piles so that this rule is never broken. In addition, they also need to pay attention to the transport capacity of the sled, since it supports a maximum of K toys.

As they are both extremely lazy, they would like to work as little as possible, so they decided to alternate their travels, so there would always be one of them resting while the other works. Also, out of laziness, they always load the sled only with gifts from a single pile, since it would be "too much work" to change the location of the sled once parked.

On the first day everything went very well, and to the surprise of both, at the end of the day they were presented with various sweets. However, as the days went by, Dali realized that Dila always made the last trip, so it was he who received the sweets, and with that he ended up getting the best ones. Suspicious, Dali began to analyze the way in which Dila decided which gifts to take, he came to the conclusion that there was a strategy behind his brother's choices, both to choose the pile and the quantity of gifts, everything was analyzed so that in the end he could have the best sweets.

Being the older brother, Dali can choose who will make the first trip, however, he noted that it is not always worth being the first, for example, assuming that there are only two stacks with the same amount of gifts, if Dali starts, any move he makes can be copied by his brother in the second pile, thus guaranteeing a victory. He is sure that there are more cases where starting could cause his defeat, and he would like to choose his brother to make the first trip in such cases.

Could you help Dali choose who should make the first trip so that, if both use the best strategies, Dali can make the last trip and keep the sweets?


The input begins with two integers N and K (1 ≤ N, K ≤ 106) representing respectively the number of piles and the number of gifts that the magic sled supports.

In the next line there are N integers Ai (1 ≤ Ai ≤ 106), where the i-th of these integers represents the number of gifts in the i-th pile. Recalling that by the rule of the elves, such integers are in non-decreasing order.


Show in the output who should make the first trip so that Dally has a chance to keep the best sweets.

Input Samples Output Samples

3 1

1 2 2


5 3

1 1 2 2 3


2 3

5 5