Вася сдал сессию! Вопреки ожиданиям, Вася совсем не устал и готов к новым подвигам. Однако, загружать себя чрезвычайно сложными задачами Вася тоже не хочет.
Вася вспомнил, что у него есть несложная головоломка: на шахматной доске размера $$$n \times n$$$ находятся $$$m$$$ цветных кубиков, причем $$$m \leq n$$$, а все цвета кубиков различны. Каждый кубик занимает ровно одну клетку. Также для каждого кубика известна клетка доски, на которую его нужно поставить. Кубики хрупкие и их очень легко разбить, поэтому за одну операцию можно только бережно передвинуть один кубик на соседнюю по стороне клетку, если она свободна. Вася настолько аккуратен, что одна операция занимает у него целую секунду.
Вася специально тренировался к финалу VK Cup, поэтому его концентрации хватает максимум на $$$3$$$ часа, то есть на $$$10800$$$ секунд. Помогите Васе найти последовательность действий, которая приведет к тому, что все кубики окажутся на соответствующих клетках, но при этом будет достаточно короткой, чтобы Вася не потерял концентрацию и не разбил кубик.
Первая строка содержит два натуральных числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 50$$$) — размер доски и количество кубиков соответственно.
Каждая из следующих $$$m$$$ строк содержит два натуральных числа $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — начальные позиции кубиков.
Следующие $$$m$$$ строк описывают конечные позиции кубиков в том же формате и в том же порядке.
Гарантируется, что все начальные позиции кубиков попарно различны, все конечные позиции кубиков попарно различны, однако, начальные позиции некоторых кубиков могут совпадать с некоторыми конечными позициями.
В первой строке вывести число $$$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$$$ должна быть пустой перед выполнением операции.
Можно показать, что хотя бы одно решение существует. Если существует несколько решений, можно вывести любое из них.
2 1
1 1
2 2
2
1 1 1 2
1 2 2 2
2 2
1 1
2 2
1 2
2 1
2
2 2 2 1
1 1 1 2
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 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
В четвертом примере выведенная последовательность действий (показана на рисунке ниже) является корректной, но не является кратчайшей. Существует решение, содержащее лишь $$$3$$$ действия.
