Джон Сноу сражается с белыми ходоками. У него есть n рейнджеров, каждый из которых имеет свою силу. Также у Джона Сноу есть любимое число x. Каждый рейнджер может сражаться с белым ходоком, если сила этого белого ходока равна его силе. Однако он думает, что его рейнджеры слабые и нуждаются в улучшении. Джон думает, что если он возьмет побитовый XOR сил некоторых рейнджеров с его любимым числом x, то он может получить солдат с более высокой силой. Итак, он решил сделать следующую операцию k раз:
- Расставить всех рейнджеров в ряд в порядке возрастания сил.
- Взять побитовый XOR (пишется как
) силы каждого второго рейнджера в ряду, начиная с самого первого, с числом x и обновить его силу.Предположим, что у Джона есть 5 рейнджеров с силами [9, 7, 11, 15, 5], и он выполняет операцию 1 раз с x = 2. Сначала он упорядочивает рейнджеров в порядке их сил, [5, 7, 9, 11, 15]. Далее он делает следующее:
- Сила первого рейнджера обновляется значением
, то есть 7. - Сила второго рейнджера остается прежней, то есть равной 7.
- Сила третьего рейнджера обновляется значением
, то есть 11. - Сила четвертого рейнджера остается прежней, то есть равной 11.
- Сила пятого рейнджера обновляется значением
, то есть 13.
Новые силы 5 рейнджеров [7, 7, 11, 11, 13].
Теперь Джон хочет знать максимальную и минимальную силу рейнджеров после выполнения операций, описанных выше, k раз. Он хочет вашей помощи по этой задаче. Можете ли вы помочь ему?
Выходные данные
Выведите два целых числа — максимальная и минимальная силы рейнджеров после выполнения k операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2
9 7 11 15 5
|
13 7
|
|
2
|
2 100000 569
605 986
|
986 605
|