Вам заданы две матрицы \(A\) и \(B\). В каждой матрице ровно \(n\) строк и \(m\) столбцов. Каждый элемент \(A\) — \(0\) или \(1\); каждый элемент \(B\) изначально равен \(0\).
Вы можете провести любое количество операций с матрицей \(B\). Для проведения операции вы должны выбрать любую подматрицу \(B\) размера \(2 \times 2\) и заменить все элементы в этой подматрице на \(1\). Иными словами, вы выбираете два целых числа \(x\) и \(y\) (\(1 \le x < n\), \(1 \le y < m\)), а затем заменяете все элементы \(B_{x, y}\), \(B_{x, y + 1}\), \(B_{x + 1, y}\) и \(B_{x + 1, y + 1}\) на \(1\).
Ваша задача — сделать матрицу \(B\) равной матрице \(A\). Две матрицы \(A\) и \(B\) равны тогда и только тогда, когда каждый элемент матрицы \(A\) равен соответствующему элементу матрицы \(B\).
Можно ли сделать матрицы равными? Если это так, вы должны найти последовательность операций, которые делают матрицу \(B\) равной матрице \(A\). Обратите внимание, что минимизировать количество операций не нужно.
Выходные данные
Если невозможно сделать \(B\) равной \(A\), выведите одно число \(-1\).
Иначе выведите любую последовательность операций, превращающую \(B\) в \(A\), в следующем формате: в первой строке выведите одно целое число \(k\) — количество операций, а затем выведите \(k\) строк, в каждой из которых должны быть два целых числа \(x\) и \(y\) для соответствующей операции (заменить все элементы \(B_{x, y}\), \(B_{x, y + 1}\), \(B_{x + 1, y}\) и \(B_{x + 1, y + 1}\) на \(1\)). Должно выполняться условие \(0 \le k \le 2500\).
Примечание
Иллюстрация к ответу на первый тест:
\(\begin{matrix} 0 & 0 & 0 & & 1 & 1 & 0 & & 1 & 1 & 1 & & 1 & 1 & 1 \\ 0 & 0 & 0 & \rightarrow & 1 & 1 & 0 & \rightarrow & 1 & 1 & 1 & \rightarrow & 1 & 1 & 1 \\ 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 0 & 0 & & 0 & 1 & 1 \end{matrix}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 1 1
1 1 1
0 1 1
|
3
1 1
1 2
2 2
|
|
2
|
3 3
1 0 1
1 0 1
0 0 0
|
-1
|
|
3
|
3 2
0 0
0 0
0 0
|
0
|