题目描述

研究员 Theo 手中有三个互不相同的长度为 $n$ 的二进制向量。他希望构造一个关于 $n$ 个布尔变量 $v_1,v_2,\ldots,v_n$ 的 2-CNF 公式，用它尽可能精确地“圈出”这三个向量。

你需要输出任意一个满足下列条件的 2-CNF 公式：

• 这个公式在给定的三个向量上均为真；
• 在所有满足上一条的 2-CNF 公式中，使公式为真的二进制向量数量尽可能少；
• 公式不能太长。

回忆一下，2-CNF 公式形如

其中每个子句 $C_i$ 是两个文字的析取

这里每个 $x_{ij}$ 是变量 $v_1,\ldots,v_n$ 中的一个；一个文字可以是变量本身，也可以是它的否定。若把某个二进制向量代入变量后公式值为 $1$，就称公式在该向量上为真。

如果存在多个合法公式，输出任意一个即可。

输入格式

第一行包含一个整数 $n$，表示三个二进制向量的长度。

接下来三行，每行包含一个长度为 $n$ 的二进制字符串，表示一个二进制向量。

保证三个向量两两不同。

输出格式

第一行输出一个整数 $m$，表示子句数量。

接下来 $m$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 个子句由两个文字组成：

• 若 $a_i>0$，第一个文字为 $v_{a_i}$；否则为 $\lnot v_{|a_i|}$；
• 若 $b_i>0$，第二个文字为 $v_{b_i}$；否则为 $\lnot v_{|b_i|}$。

这一行表示的子句是这两个文字的析取。

如果公式为空，即 $m=0$，则认为它对所有长度为 $n$ 的二进制向量都为真。

请注意，如果使用的子句过多，答案会被判为错误。

数据范围

• $2\le n\le 10^5$；
• $0\le m\le 2\cdot 10^5$；
• $1\le |a_i|,|b_i|\le n$。

样例 1

输入

5
00101
10011
11011

输出

6
-1 -3
3 1
-1 4
-4 1
5 5
-2 1

样例 2

输入

3
100
010
001

输出

3
-2 -1
-3 -1
-3 -2