F. Интервальная игра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру, в которой участвуют два интервала, $$$[l_1, r_1]$$$ и $$$[l_2, r_2]$$$, ограниченные соответственно целыми числами $$$x_1$$$ и $$$x_2$$$. Для интервалов выполнено $$$1 \le l_1 \le r_1 \le x_1$$$ и $$$1 \le l_2 \le r_2 \le x_2$$$.

Игра проходит следующим образом. За один ход игрок должен выбрать один из двух интервалов (пусть это $$$i$$$-й интервал $$$[l_i, r_i]$$$) и выполнить ровно одну из следующих операций:

  • Заменить $$$l_i$$$ на строго меньшее целое число $$$l'_i$$$ такое, что $$$1 \le l'_i \lt l_i$$$.
  • Заменить $$$r_i$$$ на строго большее целое число $$$r'_i$$$ такое, что $$$r_i \lt r'_i \le x_i$$$.
Игрок, который не может сделать допустимый ход, проигрывает.

Построение игры происходит в два шага:

  1. Сначала Алиса выбирает значения $$$l_1$$$ и $$$r_1$$$, задавая первый интервал. Он должен быть допустимым интервалом внутри $$$[1, x_1]$$$.
  2. Затем второй интервал $$$[l_2, r_2]$$$ выбирается равновероятно случайно из всех возможных допустимых интервалов внутри $$$[1, x_2]$$$.

После выбора интервалов игра начинается, и Алиса ходит первой.

Предполагая, что и Алиса, и Боб играют оптимально, Алиса хочет выбрать начальный интервал $$$[l_1, r_1]$$$ так, чтобы максимизировать вероятность своей победы. Ваша задача — найти такой интервал. Если оптимальных интервалов несколько, можно вывести любой из них.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных содержатся два целых числа $$$x_1$$$ и $$$x_2$$$ ($$$1 \le x_1, x_2 \le 5 \cdot 10^5$$$) — верхние границы для двух интервалов.

Гарантируется, что сумма значений $$$x_1$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Гарантируется, что сумма значений $$$x_2$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите два целых числа $$$l_1$$$ и $$$r_1$$$ ($$$1 \le l_1 \le r_1 \le x_1$$$) — оптимальный интервал, выбранный Алисой.

Если оптимальных интервалов несколько, можно вывести любой из них.

Пример
Входные данные
6
1 1
1 10
2 1
2 2
20 64578
185367 133524
Выходные данные
1 1
1 1
2 2
1 2
5 12
37381 52023
Примечание

Для первого набора входных данных Алиса вынуждена выбрать $$$[1, 1]$$$, так как это единственный допустимый вариант.

Для третьего набора входных данных, если Алиса выберет $$$[2, 2]$$$, она гарантированно выиграет (вероятность $$$1$$$); она может заменить $$$l_1$$$ на $$$1$$$, после чего Боб не сможет сделать допустимый ход. Заметим, что $$$[1, 1]$$$ тоже был бы здесь корректным выигрышным ответом.

Для четвертого набора входных данных, если Алиса выберет $$$[1, 2]$$$, она получит вероятность победы $$$2/3$$$. В то же время выбор $$$[1, 1]$$$ или $$$[2, 2]$$$ даст вероятность победы только $$$1/3$$$.