题目描述

问题描述

在 AtCoder 王国中有 $2\times N$ 个交叉口，每个交叉口编号从 $1$ 到 $2\times N$。此外，在 AtCoder 王国中有以下 $3$ 种单向道路：

• 类型 A: 对于 $2 \leq i \leq N$，从交叉口 $2i-3$ 到交叉口 $2i-1$ 的道路
• 类型 B: 对于 $2 \leq i \leq N$，从交叉口 $2i-2$ 到交叉口 $2i$ 的道路
• 类型 C: 对于 $1 \leq i \leq N$，连接交叉口 $2i-1$ 和交叉口 $2i$ 的方向为 $s_i$ 的道路

这里，$s_i$ 是 X 或 Y，其中 X 表示从交叉口 $2i-1$ 到交叉口 $2i$ 的方向，而 Y 表示从交叉口 $2i$ 到交叉口 $2i-1$ 的方向。

高桥君希望通过进行步行几次，对于每个 $1 \leq i \leq N$，使连接交叉口 $2i-1$ 和交叉口 $2i$ 的类型 C 道路的方向为 $t_i$。

步行操作 从任意交叉口出发，重复以下操作 $0$ 次或多次：

• 如果可以走上类型 C 的道路，则沿着该道路走到下一个交叉口。
• 如果无法走上类型 C 的道路，但可以走上类型 A 或 B 的道路，则沿着该道路走到下一个交叉口。

然后，将经过的所有类型 C 的道路的方向反转。

请计算达到目的所需的最少步行次数，并给出达到目的的最少步行次数的方法。在此问题的约束条件下，可以证明可以有限次步行达到目的地。

输入格式

以以下形式输入数据：

$N$

$s_1\ s_2\ \cdots\ s_N$

$t_1\ t_2\ \cdots\ t_N$

输出格式

请以以下形式输出。假设步行次数为 $X$。此外，第 $i$ 次步行（$1 \leq i \leq X$）从交叉口 $a_i$ 出发，最终在交叉口 $b_i$ 终止。

$X$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_X$ $b_X$

样例 1

输入

5
XYXYX
XXYXX

输出

1
2 7

样例 2

输入

5
XXYYX
XXYYX

输出

0

样例 3

输入

5
XXXXX
YYYYY

输出

5
1 2
3 4
5 6
7 8
9 10

样例 4

输入

20
XXXYXYYXXXYXXXXYYXXY
XXYXYYXXYXXYXYXYXYXY

输出

5
14 18
29 38
14 26
5 10
27 35

样例 5

输入

20
YXYXYXYYYXYYXYYXYXXX
XXXXXYXYYYXYYXXYYYXY

输出

5
29 36
10 38
2 3
4 7
28 40

说明/提示

• $N$ 是满足 $1 \leq N \leq 4000$ 的整数
• $s_1, s_2, \dots, s_N$ 是 X 或 Y
• $t_1, t_2, \dots, t_N$ 是 X 或 Y

【样例解释 1】

在这个样例中，高桥君将按照以下步骤行走：

• 从交叉口 2 出发。
• 由于从交叉口 2 没有类型 C 道路可供前进，沿着类型 B 道路走到交叉口 4。
• 由于从交叉口 4 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 3。
• 由于从交叉口 3 没有类型 C 道路可供前进，沿着类型 A 道路走到交叉口5。
• 由于从交叉口 5 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 6。
• 由于从交叉口 6 没有类型 C 道路可供前进，沿着类型 B 道路走到交叉口 8。
• 由于从交叉口 8 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 7。
• 在交叉口 7 结束。

这次步行经过了以下三条类型 C 道路：

• 连接交叉口 3 和交叉口 4 的道路。
• 连接交叉口 5 和交叉口 6 的道路。
• 连接交叉口 7 和交叉口 8 的道路。

这些道路的方向被反转，因此连接交叉口 $2i−1$ 和交叉口 $2i$（其中 $i=1,2,3,4,5$）的道路的方向现在分别为 X、X、Y、X、X，到达了目的地。