C. Джон Сноу и его любимое число
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джон Сноу сражается с белыми ходоками. У него есть n рейнджеров, каждый из которых имеет свою силу. Также у Джона Сноу есть любимое число x. Каждый рейнджер может сражаться с белым ходоком, если сила этого белого ходока равна его силе. Однако он думает, что его рейнджеры слабые и нуждаются в улучшении. Джон думает, что если он возьмет побитовый XOR сил некоторых рейнджеров с его любимым числом x, то он может получить солдат с более высокой силой. Итак, он решил сделать следующую операцию k раз:

  1. Расставить всех рейнджеров в ряд в порядке возрастания сил.
  2. Взять побитовый XOR (пишется как ) силы каждого второго рейнджера в ряду, начиная с самого первого, с числом x и обновить его силу.

    Предположим, что у Джона есть 5 рейнджеров с силами [9, 7, 11, 15, 5], и он выполняет операцию 1 раз с x = 2. Сначала он упорядочивает рейнджеров в порядке их сил, [5, 7, 9, 11, 15]. Далее он делает следующее:

    1. Сила первого рейнджера обновляется значением , то есть 7.
    2. Сила второго рейнджера остается прежней, то есть равной 7.
    3. Сила третьего рейнджера обновляется значением , то есть 11.
    4. Сила четвертого рейнджера остается прежней, то есть равной 11.
    5. Сила пятого рейнджера обновляется значением , то есть 13.

    Новые силы 5 рейнджеров [7, 7, 11, 11, 13].

    Теперь Джон хочет знать максимальную и минимальную силу рейнджеров после выполнения операций, описанных выше, k раз. Он хочет вашей помощи по этой задаче. Можете ли вы помочь ему?

Входные данные

Первая строка содержит три целых числа n, k, x (1 ≤ n ≤ 105, 0 ≤ k ≤ 105, 0 ≤ x ≤ 103) — количество рейнджеров у Джона, количество раз, которое Джон выполнит операцию, описанную выше, и любимое число Джона соответственно.

Вторая строка содержит n целых чисел, обозначающих силы рейнджеров, a1, a2, ..., an (0 ≤ ai ≤ 103).

Выходные данные

Выведите два целых числа — максимальная и минимальная силы рейнджеров после выполнения k операций.

Примеры
Входные данные
5 1 2
9 7 11 15 5
Выходные данные
13 7
Входные данные
2 100000 569
605 986
Выходные данные
986 605