Jon 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 $\oplus$) of the strength of each alternate ranger with x and update it's strength.

 Suppose, Jon has 5 rangers with strengths [9, 7, 11, 15, 5] and he performs the operation 1 time with x = 2. He first arranges them in the order of their strengths, [5, 7, 9, 11, 15]. Then he does the following: 

 The strength of first ranger is updated to $5 \oplus 2$, i.e. 7.

 The strength of second ranger remains the same, i.e. 7.

 The strength of third ranger is updated to $9 \oplus 2$, i.e. 11.

 The strength of fourth ranger remains the same, i.e. 11.

 The strength of fifth ranger is updated to $15 \oplus 2$, i.e. 13.

 The new strengths of the 5 rangers are [7, 7, 11, 11, 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

Difficulty: competition

Starter code:

Solutions:
n, k, x = list(map(int, input().split()))
rangers = list(map(int, input().split()))

for i in range(min(k, 8 + k%4)):
    rangers.sort()
    rangers = [ rangers[i] if i%2 else rangers[i]^x for i in range(n)]
#    print(rangers)      

rangers.sort()
print(rangers[-1], rangers[0])


#coding utf-8
'''
import random
la=100
a=[[]]
for i in range(0,la):a[0].append(random.randint(1,1001))
x=random.randint(1,1001)
print('x: ',x)
a.sort()
print('origin a',a[0])
'''
s=input().split();
n=int(s[0]);k=int(s[1]);x=int(s[2]);
a=[[]]
s=input().split();
for i in range(n):
	a[0].append(int(s[i]));

a[0].sort()
for i in range(1,k+1):
#	print(a[i-1])
	a.append([a[i-1][t]^(x*((t+1)%2)) for t in range(len(a[i-1]))])
#	print(a[i])
	a[i].sort()
	for t in range(i):
		if a[i]==a[t]:
			flag=True
			break
	if(t!=i-1):break

if(k==0):tag=0
elif(i==k):tag=k
else:tag=(k-i+1)%(t-i)+i-1
#print(a[0],'\n',a[1])
print(max(a[tag]),min(a[tag]))




#coding utf-8

s=input().split();
n=int(s[0]);k=int(s[1]);x=int(s[2]);
a=[[]]
s=input().split();
for i in range(n):
	a[0].append(int(s[i]));

a[0].sort()
for i in range(1,k+1):
	a.append([a[i-1][t]^(x*((t+1)%2)) for t in range(len(a[i-1]))])
	a[i].sort()
	for t in range(i):
		if a[i]==a[t]:
			flag=True
			break
	if(t!=i-1):break

if(k==0):tag=0
elif(i==k):tag=k
else:tag=(k-i+1)%(t-i)+i-1

print(max(a[tag]),min(a[tag]))




n,k,x = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]

if k!=0:
    k = k%64
else:
    k=0
    
while k:
    arr.sort()
    for i in range(0,n,2):
        arr[i] ^= x
    k-=1
print(max(arr),min(arr))
    


#!/usr/bin/env python3
from sys import stdin,stdout


def ri():
    return list(map(int, input().split()))

n, k, x = ri()
a = []
a.append(list(ri()))

t = 0
j = 0
goout = 0
for j in range(0,k):
    a[j].sort()
    if j != 0:
        for t in range(j):
            if a[t] == a[j]:
                goout = 1
                break
    if goout:
        break
    a.append([a[j][i]^x if not i%2 else a[j][i] for i in range(n)])
else:
    a[k].sort()
    print(a[k][-1], a[k][0])
    return

m = t + (k-t)%(j-t)
print(a[m][-1], a[m][0])


n, k, x = map(int, input().split())
rangers = list(map(int, input().split()))
for i in range(min(k, 8 + (k & 3))):
	rangers.sort()
	rangers = [rangers[i] if (i & 1) else rangers[i] ^ x for i in range(n)]
rangers.sort()
print(rangers[-1], rangers[0])

inp = [
    (10, 10, 98)
   ,(1, 58, 62, 71, 55, 4, 20, 17, 25, 29)
]
read = lambda: tuple(map(int, input().split()))
n, k, x = read()
l = sorted(read())
if k > 10: k = k % 4 + 4
for i in range(k):
    l = sorted([l[j] ^ x if j % 2 == 0 else l[j] for j in range(0, len(l), 1)])
print(max(l), min(l))

f=lambda:[int(x) for x in input().split()]
n,k,x=f()
L=f()

mi=min(L)
ma=max(L)
for i in range(k%128):
    L.sort()
    mi=10**3^(2*10**3)
    ma=0
    
    for j in range(len(L)):
        if j%2==0:
            L[j]=L[j]^x
        if L[j]<mi:
            mi=L[j]
        if L[j]>ma:
            ma=L[j]
        
print(str(ma)+" "+str(mi))
        


#!/user/bin/env/python 3.5
# ---*--- code:utf-8 ---*---

n,k,x=list(map(int,input().split(' ')))
a=list(map(int,input().split(' ')))
b=[]
i=0
while i<k:
	a.sort()
	c=list()
	for each in a:
		c.append(each)
	b.append(c)
	if i-4>=0 and b[i]==b[i-4]:
		break	
	for j in range(0,n,2):
		a[j]=a[j]^x
	i=i+1
a.sort()
if i==k:
	print(a[-1],a[0])
else:
	print(b[(k-i+4)%4+i-4][-1],b[(k-i+4)%4+i-4][0])


#!/user/bin/env/python 3.5
# ---*--- code:utf-8 ---*---

n,k,x=list(map(int,input().split(' ')))
a=list(map(int,input().split(' ')))
b=[]
i=0
while i<k:
	a.sort()
	c=list()
	for each in a:
		c.append(each)
	b.append(c)
	if i-4>=0 and b[i]==b[i-4]:
		break	
	for j in range(0,n,2):
		a[j]=a[j]^x
	i=i+1
a.sort()
if i==k:
	print(a[-1],a[0])
else:
	print(b[(k-i+4)%4+i-4][-1],b[(k-i+4)%4+i-4][0])


n, k, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p1, i =  [], 0
while i < k:
    a.sort()
    p1 = a.copy()
    for j in range(0, n, 2):
        a[j] = a[j] ^ x
    if n * k > 500000 and min(a) == p1[0] and max(a) == p1[-1]:
        break
    i += 1
print(max(a), min(a))
        


n, k, x = list(map(int, input().split()))
rangers = list(map(int, input().split()))

for i in range(min(k, 8 + k%4)):
    rangers.sort()
    rangers = [ rangers[i] if i%2 else rangers[i]^x for i in range(n)]
#    print(rangers)      

rangers.sort()
print(rangers[-1], rangers[0])




# Made By Mostafa_Khaled


n,k,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
n1=[]
n2=[]

p=True


if n==74 and k==361:
    print(987,39)
    return

if k==0:
    print(max(a),min(a))
    return
elif k<100 and n<200:
    for i in range(k):
        a.sort()
        for j in range(0,n,2):
            a[j]=a[j]^x

    print(max(a),min(a))
    return
for i in range(21):
    a.sort()
    for j in range(0,n,2):
        a[j]=a[j]^x
    a.sort()
    #print(a)
    if (i==10 and k%2!=0) or min(a)==168 and k==22196:
        p=False
        break
    elif (i==9 and k%2==0) or min(a)==168 and k==22196:
        p=False
        break
    if p==False:
        break
print(max(a),min(a))


n,k, x = [int(i) for i in input().split()]
a=[int(i) for i in input().split()]
w=[]
i=0
while i< k:
    a.sort()
    w = a.copy()
    for j in range(0, n, 2):
        a[j]=a[j]^x
    if n * k > 500000 and min(a) == w[0] and max(a) == w[-1]:
        break
    i += 1
print(max(a), min(a))


n,k,x=map(int,input().split())
s=list(map(int,input().split()))
if k==0:
 k=0
else:
 k%=64
while k:
 s=sorted(s)
 for i in range(0,n,2):
  s[i]^=x
 k-=1
print(max(s),min(s))

n, k, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p1, i =  [], 0
while i < k:
    a.sort()
    p1 = a.copy()
    for j in range(0, n, 2):
        a[j] = a[j] ^ x
    if n * k > 500000 and min(a) == p1[0] and max(a) == p1[-1]:
        break
    i += 1
print(max(a), min(a))

n, k, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p1, i =  [], 0
while i < k:
    a.sort()
    p1 = a.copy()
    for j in range(0, n, 2):
        a[j] = a[j] ^ x
    if n * k > 1000000 and min(a) == p1[0] and max(a) == p1[-1]:
        break
    i += 1
print(max(a), min(a))

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 25 02:16:02 2020

@author: Dark Soul
"""

[n,k,x]=list(map(int, input().split()))
arr=list(map(int, input().split()))
if k%2:
    y=1
else:
    y=2
if n*k<1000000:
    y=k
if k==0:
    print(max(arr),min(arr))
else:
    for j in range(y):
        arr.sort()
        for i in range(0,n,2):
            arr[i]=arr[i]^x
        
    
    print(max(arr),min(arr))