Boys in the Assembly

Limits 1s, 512 MB

N boys are standing in the assembly. There is a single line only. Boys are denoted by their roll numbers. The first and second boy in the assembly line always keep quarreling with each other. So every time they do this, a teacher rotates the line. Which means, the boy who is standing at position 1 goes to the end, all other boys goes to (i-1)'th position from i'th position.

Print the roll numbers of boys who are standing at the first and last position after R rotations.

Input

The first line of the input contains two integers N (2 ≤ N ≤ 106) and R (0 ≤ R ≤ 108).

The second line of the input contains N integers, Ai (1 ≤ Ai ≤ 106).

Output

Print the roll numbers of boys standing at the first and last position after R rotations.

Samples

InputOutput
4 1
1 2 3 4
2 1
InputOutput
3 3
2 3 1
2 1

Array elements (boys' roll numbers) are 1-indexed.

In the second test case there are 3 rotations.

So the answer will be 2 1