Description

有两个 $n\times m$ 大小的扫雷地图。你可以进行不超过 $K=5\times10^5$ 次如下操作：任选一个地图的一个位置，若这个位置是雷，则改成空位；否则在这个位置放一个雷。操作完成后，按照扫雷的规则在两个图的所有空位上填上 $0\sim 8$ 的数字（表示与这个位置八联通的位置中有多少个雷）。你需要使两个地图填上的数字和相等。

若不存在 $K$ 次操作以内的方案，输出 $-1$.

Format

Input

第一行输入两个正整数 $n,m\quad(1\leq n,m\leq 1000)$，表示两个地图的大小。

随后输入两个地图，地图按输入顺序分别记作 $1$ 号地图和 $2$ 号地图。对于每个地图，输入一个 $n$ 行 $m$ 列的字符方阵，字符为 . 或 #，其中 . 表示这个位置是空位；# 表示这个位置有雷。

Output

若 $K$ 次操作以内没有这样的方案 ，仅输出一个数 $-1$.

否则，第一行输出一个非负整数 $t$ 表示操作的次数。

随后 $t$ 行，每行三个整数 $id,i,j$，以空格隔开，表示在 $id$ 号地图，第 $i$ 行第 $j$ 列的位置进行一次操作。

Sample

3 5
..#..
#....
....#
..##.
.....
....#

1
2 2 4

Limitation

本题有捆绑测试。请注意，当一个 subtask 的一个数据点出现非 Accepted 的评测结果时，该 subtask 的其它数据点会不予评测（即 cancelled）。

2s, 256MiB.