Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии \(m\) равно \(2\). Вы можете делать взломы только в том случае, если решили все версии этой задачи.
В Древнем Египте проходит соревнование по решению задач с \(n\) участниками, пронумерованными от \(1\) до \(n\). Каждый участник представляет определенный город; города пронумерованы от \(1\) до \(m\). Из каждого города есть как минимум один участник.
У \(i\)-го участника есть сила \(a_i\), специализация \(s_i\) и мудрость \(b_i\), при этом \(b_i \ge a_i\). Каждая задача в соревновании будет иметь некоторую сложность \(d\) и уникальную тему \(t\). \(i\)-й участник решит задачу, если
- \(a_i \ge d\), т.е. его сила не меньше сложности задачи, или
- \(s_i = t\), и \(b_i \ge d\), т.е. его специализация соответствует теме задачи, и его мудрость не меньше сложности задачи.
Хеопс хочет выбрать задачи таким образом, чтобы каждый участник из города \(i\) решил строго больше задач, чем каждый участник из города \(j\), для всех \(i < j\).
Пожалуйста, найдите набор из не более чем \(5n\) задач, где темы всех задач попарно различны, чтобы воля Хеопса была удовлетворена, или укажите, что это невозможно.
Выходные данные
Если существует набор задач, который удовлетворяет условиям Хеопса, то в первой строке выведите одно целое число \(p\) (\(1 \le p \le 5n\)) — количество задач в вашем решении.
Затем выведите \(p\) строк, каждая из которых содержит два целых числа \(d\) и \(t\) (\(0 \le d, t \le {10}^9\)) — сложность и тема соответствующей задачи. Темы должны быть различными.
Если нет набора задач, который соответствует желаниям Хеопса, выведите \(-1\) вместо этого.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 2
5 7 1
6 7 2
3 9 2
5 10 3
4 4 1
2 1 2
3 3 4 5
2 2
1 2 1
1 2 1
1 2
1 1
|
7
6 4
6 5
5 6
5 7
4 8
4 9
7 1
-1
|