Вася сдал сессию! Вопреки ожиданиям, Вася совсем не устал и готов к новым подвигам. Однако, загружать себя чрезвычайно сложными задачами Вася тоже не хочет.
Вася вспомнил, что у него есть несложная головоломка: на шахматной доске размера \(n \times n\) находятся \(m\) цветных кубиков, причем \(m \leq n\), а все цвета кубиков различны. Каждый кубик занимает ровно одну клетку. Также для каждого кубика известна клетка доски, на которую его нужно поставить. Кубики хрупкие и их очень легко разбить, поэтому за одну операцию можно только бережно передвинуть один кубик на соседнюю по стороне клетку, если она свободна. Вася настолько аккуратен, что одна операция занимает у него целую секунду.
Вася специально тренировался к финалу VK Cup, поэтому его концентрации хватает максимум на \(3\) часа, то есть на \(10800\) секунд. Помогите Васе найти последовательность действий, которая приведет к тому, что все кубики окажутся на соответствующих клетках, но при этом будет достаточно короткой, чтобы Вася не потерял концентрацию и не разбил кубик.
Выходные данные
В первой строке вывести число \(k\) (\(0 \le k \leq 10800\)) — количество действий Васи. В каждой из следующих \(k\) строк нужно описать одно действие — вывести четыре целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\), где \(x_1, y_1\) — позиция кубика, который двигает Вася, \(x_2, y_2\) — новая позиция этого кубика. Клетки \(x_1, y_1\) и \(x_2, y_2\) должны быть соседними по стороне, клетка \(x_2, y_2\) должна быть пустой перед выполнением операции.
Можно показать, что хотя бы одно решение существует. Если существует несколько решений, можно вывести любое из них.
Примечание
В четвертом примере выведенная последовательность действий (показана на рисунке ниже) является корректной, но не является кратчайшей. Существует решение, содержащее лишь \(3\) действия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 1
2 2
|
2
1 1 1 2
1 2 2 2
|
|
2
|
2 2
1 1
2 2
1 2
2 1
|
2
2 2 2 1
1 1 1 2
|
|
3
|
2 2
2 1
2 2
2 2
2 1
|
4
2 1 1 1
2 2 2 1
1 1 1 2
1 2 2 2
|
|
4
|
4 3
2 2
2 3
3 3
3 2
2 2
2 3
|
9
2 2 1 2
1 2 1 1
2 3 2 2
3 3 2 3
2 2 1 2
1 1 2 1
2 1 3 1
3 1 3 2
1 2 2 2
|