Отель «Континенталь»
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Отель «Континенталь», в котором случается достаточно много ключевых событий в жизни Джона Уика, имеет долгую историю. И построен он был, несмотря на все ресурсы Правления Кланов и Старейшины, не в один день.

Всего отдель был построен за $$$n$$$ дней. В первый день было построено основание «Континенталя» в виде прямоугольника размером $$$a_1 \times b_1$$$. Затем в $$$i$$$-й день к текущему основанию с краю достраивался еще один блок размером $$$a_i \times b_i$$$ так, чтобы основание оставалось прямоугольником.

Иными словами, текущее основание и прямоугольник размером $$$a_i \times b_i$$$ присоединялись друг к другу одинаковой стороной. Прямоугольник мог быть повернут на $$$90^\circ$$$ и присоединен к любой из сторон текущего основания, если сам имел равную ей сторону.

Джон, чтобы незаметно пробраться в «Континенталь» к Винстону, добыл записи о всех $$$n$$$ днях постройки. Теперь он хочет понять, правдивы ли эти записи, и, если да, какими могут быть размеры текущего «Континенталя».

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

В первой строке ввода дано единственное число $$$n$$$ — количество дней постройки отеля ($$$1 \leqslant n \leqslant 10^5$$$).

В $$$i$$$-й из следующих $$$n$$$ строк через пробел даны два целых числа $$$a_i$$$ и $$$b_i$$$ — размеры прямоугольника, присоединяемого к основанию в $$$i$$$-й день ($$$1 \leqslant a_i, b_i \leqslant 10^{12}$$$). Обратите внимание, что размеры прямоугольников могут не помещаться в $$$32$$$-битный целочисленный тип данных int.

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

В первой строке выведите одно целое число $$$k$$$ — количество возможных вариантов размеров «Континенталя». Если в записях есть ошибка, и отель не мог быть построен из указанных прямоугольников, считайте, что $$$k = 0$$$.

В $$$i$$$-й из следующих $$$k$$$ строк выведите через пробел два числа — размеры отеля в $$$i$$$-м варианте.

Варианты можно выводить в любом порядке. На одной строке длину и ширину также можно вывести в любом порядке.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
117$$$n \leqslant 2$$$полная
213$$$a_i = b_i$$$ для всех $$$i$$$полная
319$$$n \leqslant 3$$$1первая ошибка
422$$$a_i$$$ и $$$b_i$$$ — степени двойки для всех $$$i$$$первая ошибка
529нет1 – 4первая ошибка

Примеры

Входные данные
3
2 2
2 3
2 4
Выходные данные
1
2 9
Входные данные
3
2 2
2 3
3 4
Выходные данные
0
Входные данные
4
2 3
3 2
3 6
5 10
Выходные данные
2
5 16
8 10