Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Jon Snow and his Favourite Number

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJon Snow now has to fight with White Walkers. He has *n* rangers, each of which has his own strength. Also Jon Snow has his favourite number *x*. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to improve. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number *x*, he might get soldiers of high strength. So, he decided to do the following operation *k* times:

- Arrange all the rangers in a straight line in the order of increasing strengths.
- Take the bitwise XOR (is written as ) of the strength of each alternate ranger with
*x*and update it's strength.

- The strength of first ranger is updated to , i.e. 7.
- The strength of second ranger remains the same, i.e. 7.
- The strength of third ranger is updated to , i.e. 11.
- The strength of fourth ranger remains the same, i.e. 11.
- The strength of fifth ranger is updated to , i.e. 13.

Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations *k* times. He wants your help for this task. Can you help him?

Input

First line consists of three integers *n*, *k*, *x* (1 ≤ *n* ≤ 10^{5}, 0 ≤ *k* ≤ 10^{5}, 0 ≤ *x* ≤ 10^{3}) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.

Second line consists of *n* integers representing the strengths of the rangers *a*_{1}, *a*_{2}, ..., *a*_{n} (0 ≤ *a*_{i} ≤ 10^{3}).

Output

Output two integers, the maximum and the minimum strength of the rangers after performing the operation *k* times.

Examples

Input

5 1 2

9 7 11 15 5

Output

13 7

Input

2 100000 569

605 986

Output

986 605

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 05:30:18 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|