One of Ashley and Oleg's presents was a board game called Konnect, which is a game where two players take turns dropping pieces of their color into a 2D grid and the first person to get ~K~ pieces of their color in a row horizontally, vertically, or diagonally wins.
Ashley and Oleg recorded the sequence of moves that were played during one of their games, but they have since forgotten the result of the game. Could you help figure out who won?
The input begins with two integers ~N, K~ ~(1 \le N, K \le 300\ 000)~, the number of moves that were played and the value ~K~. The next line contains ~N~ integers ~C_i~ ~(1 \le C_i \le 10^6)~, which say that the ~i~-th move was played in column ~C_i~. The two players alternate making moves, with Ashley going first.
For 30% of cases, ~N \le 100, C_i \le 1,000~.
For 50% of cases, ~K \le 10~.
Output the winner of the game (
Oleg) as well as the turn on which the game ended (it is possible the game ends before the last move). It is guaranteed that the game ends with a winner.
Sample Input 1
8 4 1 2 1 2 1 2 1 2
Sample Output 1
Sample Input 2
4 2 1 1 1 2
Sample Output 2