Розділення королівства#6285

Розділення королівства

2 секунди

256 мегабайтів

Дуже легка

Королівство Флатландія розташоване на нескінченній двовимірній площині. У цьому королівстві є $n$ замків. Для зручності картографування у Флатландії використовується Декартова система координат. Відомо, що $i$ -й замок знаходиться в точці з координатами ( $x_{i} + 0.5$ x_i+0.5, $y_{i} + 0.5$ y_i+0.5), де $x_{i}$ x_i та $y_{i}$ y_i — цілі числа. Місцезнаходження всіх замків є унікальним.

На схилі років король вирішив поділити королівство між своїми синами за допомогою прямих, паралельних осям координат. Якщо пряма паралельна осі $O x$ , то $y$ -координата всіх точок на цій прямій має бути цілим числом; якщо ж пряма паралельна осі $O y$ , то $x$ -координата всіх точок має бути цілим числом. У обох випадках цілі координати не повинні перевищувати за модулем $2 \cdot 1 0^{9}$ 2 \cdot 10^9. Король бажає, щоб після поділу будь-які два замки опинилися в різних частинах.

Допоможіть королю розділити королівство, використовуючи не більше ніж $n - 1$ n-1 прямих. Жодна пара прямих не повинна мати більше однієї спільної точки.

Вхідні дані

У першому рядку дано ціле число $n$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000) — кількість замків у королівстві. У наступних $n$ рядках наведено по два числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 1 0^{9} \leq x_{i} \leq 1 0^{9}$ -10^9 \leq x_i \leq 10^9, $- 1 0^{9} \leq y_{i} \leq 1 0^{9}$ -10^9 \leq y_i \leq 10^9) — цілі частини координат замків.

Вихідні дані

У першому рядку вихідного файлу виведіть кількість використаних прямих. У наступних рядках виведіть самі прямі, по одній у кожному рядку. Якщо пряма паралельна осі $O x$ , виведіть символ " $y$ ", а потім через пробіл $y$ -координату всіх точок на цій прямій; якщо пряма паралельна осі $O y$ , виведіть символ " $x$ ", а потім через пробіл $x$ -координату всіх точок на цій прямій.

Приклади

Приклад 1