Лабиринт Минотавра представляет из себя прямоугольную таблицу, состоящую из $$$n$$$ строк и $$$m$$$ столбцов. Строки пронумерованы целыми числами от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — целыми числами от $$$1$$$ до $$$m$$$ слева направо. В каждой клетке лабиринта находится либо стена, либо пустое пространство.
Вы выведали у Дедала секретную информацию — про каждую диагональ таблицы вам известна четность количества стен на этой диагонали.
Для спасения Минотавра вам нужно построить любой лабиринт с заданной четностью количества стен на каждой диагонали. Дерзайте!
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 10^5$$$) — количество строк и столбцов в лабиринте, соответственно.
Вторая строка содержит $$$n + m - 1$$$ целых чисел $$$a_i$$$ — четность количества стен на диагоналях, идущих вправо-вверх.
Третья строка содержит $$$n + m - 1$$$ целых чисел $$$b_i$$$ — четность количества стен на диагоналях, идущих вправо-вниз.
Диагонали обоих типов нумеруются начиная с угла верхней строки таблицы. Для лучшего понимания нумерации диагоналей обратите внимание на изображение ниже:
В случае, если подходящего лабиринта не существует, в качестве ответа выведите число $$$-1$$$.
В противном случае в первой строке выведите число $$$k$$$ ($$$0 \le k \le 10^6$$$) — количество клеток лабиринта, в которых находится стена.
В каждой из следующих $$$k$$$ строк выведите через пробел два целых числа $$$r_i$$$ и $$$c_i$$$ — номер строки и столбца, на пересечении которых находится $$$i$$$-я стена лабиринта.
Все клетки $$$(r_i, c_i)$$$ должны быть попарно различны. Если существует несколько решений, выведите любое из них.
Можно показать, что при данных ограничениях, если существует какое-либо решение, то существует и решение, в котором количество стен не превышает $$$10^6$$$. Обратите внимание, что от вас не требуется минимизировать количество стен в лабиринте.
2 3 0 1 1 1 1 0 0 0
3 1 2 1 3 2 3
2 2 0 1 0 1 0 1
-1
3 3 0 0 0 0 0 0 0 0 0 0
0
3 3 1 1 0 1 0 0 0 0 0 1
5 1 1 2 1 2 2 3 1 3 2
На изображении ниже приведено решение для первого примера. Серым цветом обозначены клетки, в которых находятся стены.
В четвертом примере существует два подходящих лабиринта. Оба варианта изображены ниже:
