题目描述

有一个 $n$ 行 $m$ 列的棋盘，其中一些格子已经被挖去。

你要使用蓝色和黄色两种染料粉刷棋盘。先给每一行涂一层颜色，再给每一列涂一层颜色，因此每个未被挖去的格子都会被涂两次。

令第 $i$ 行所使用染料的颜色为 $a_i$，第 $j$ 列所使用染料的颜色为 $b_j$。每种颜色只能是蓝色或黄色。

部分 $a_i$ 和 $b_j$ 已经确定，其余颜色由你决定。

对于一个未被挖去的格子 $(i,j)$：

• 若 $a_i=b_j$，两次染料颜色相同，该格子不会变成绿色；
• 若 $a_i\ne b_j$，蓝色和黄色混合，该格子会变成绿色。

你的目标是使所有未被挖去的格子最终均为绿色。在涂色之前，你可以执行若干次以下操作：

• 选择一行或一列，将这一整行或这一整列的所有格子挖去。

请最小化操作次数，并输出一种合法方案。

输入格式

第一行输入两个正整数 $n,m$。

接下来 $n$ 行，每行输入一个长度为 $m$、仅包含字符 0 和 1 的字符串 $s_i$：

• $s_{i,j}=0$ 表示格子 $(i,j)$ 已经被挖去；
• $s_{i,j}=1$ 表示格子 $(i,j)$ 尚未被挖去。

接下来一行输入一个长度为 $n$、仅包含字符 0、1 和 2 的字符串 $A$：

• $A_i=0$ 表示第 $i$ 行必须使用蓝色染料；
• $A_i=1$ 表示第 $i$ 行必须使用黄色染料；
• $A_i=2$ 表示第 $i$ 行的颜色尚未确定。

最后一行输入一个长度为 $m$、仅包含字符 0、1 和 2 的字符串 $B$：

• $B_j=0$ 表示第 $j$ 列必须使用蓝色染料；
• $B_j=1$ 表示第 $j$ 列必须使用黄色染料；
• $B_j=2$ 表示第 $j$ 列的颜色尚未确定。

输出格式

第一行输出一个非负整数 $q$，表示最少操作次数。

第二行输出一个长度为 $n$、仅包含字符 0 和 1 的字符串，表示所有行最终使用的颜色。字符 0 表示蓝色，字符 1 表示黄色。

第三行输出一个长度为 $m$、仅包含字符 0 和 1 的字符串，表示所有列最终使用的颜色。字符 0 表示蓝色，字符 1 表示黄色。

输出的颜色必须与输入中已经确定的颜色一致。

接下来输出 $q$ 行，每行包含两个整数 $t,p$，表示一次挖除操作：

• $t=0$ 时，挖去第 $p$ 行，此时 $1\le p\le n$；
• $t=1$ 时，挖去第 $p$ 列，此时 $1\le p\le m$。

完成所有操作后，对于每个仍未被挖去且原本满足 $s_{i,j}=1$ 的格子 $(i,j)$，必须有 $a_i\ne b_j$。

由于本题采用 Special Judge，只要操作次数最少且方案合法，输出任意一种方案均可。

样例 1

2 3
011
101
02
102

1
00
101
1 2

样例 1 解释

该方案挖去了第 $2$ 列，并将第 $2$ 行确定为蓝色、第 $3$ 列确定为黄色。

下面也是一种合法输出：

1
00
101
0 1

该方案改为挖去第 $1$ 行。可以证明，最少操作次数为 $1$。

样例 2

2 3
111
111
02
122

0
00
111

样例 2 解释

不需要挖去任何行或列。可以证明该样例的最少操作次数为 $0$。

数据范围

对于所有测试数据：

• $1\le n,m\le 10^3$；
• $s_{i,j}\in\{0,1\}$；
• $A_i,B_j\in\{0,1,2\}$。

原题各测试点特殊性质如下：

特殊性质 A：每个 $s_{i,j}$ 在集合 $\{0,1\}$ 中均匀随机选取，每个 $A_i,B_j$ 在集合 $\{0,1,2\}$ 中均匀随机选取。