28549번 - Отель <<Континенталь>> 스페셜 저지다국어

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

Всего отдель был построен за $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$-м варианте.

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