XOR пары
Для заданных неотрицательных целых чисел X, A, B рассмотрим все пары неотрицательных целых чисел (a, b) таких что a xor b = X, a ≥ A и b ≥ B. Через a xor b обозначена операция исключающего или ("xor" в Паскале, "ˆ" в C/C++/Java). Отсортируем пары по возрастанию. Пары с одинаковым значением a отсортируем по возрастанию b.
Необходимо найти N-ую пару среди них. Нумерация пар начинается с 1. Будьте готовы ответить на тысячи таких вопросов для заданных X, A, B.
Входные данные
Первая строка содержит четыре целых числа X, A, B и T - количество тестов. Каждая из следующих T строк содержит положительное целое N. Известно, что 0 ≤ X, A, B ≤ 10^18, 1 ≤ T ≤ 10000 и 1 ≤ N ≤ 10^18.
Выходные данные
Для каждого значения N вывести два целых числа a и b таких, что пара (a, b) является N-ой парой среди описанной последовательности пар.