Cki86201 Container Creator (CCC) 制造两种集装箱。一种集装箱的容量为 1 吨，另一种容量为 2 吨。CCC 目前在仓库中拥有 $N$ 个排成一行的集装箱。为了运输这些集装箱，最好将先运输的集装箱放在最前面。因此，CCC 打算重新排列这 $N$ 个集装箱。

为了重新排列集装箱，我们使用机器。该机器可以选取两个或三个连续的集装箱，并将它们的顺序反转。使用机器的成本是所选集装箱的总容量加上基础成本 $C$。因此，反转两个集装箱 $[2, 1]$ 的成本为 $3 + C$，反转三个集装箱 $[1, 1, 2]$ 的成本为 $4 + C$。数字 $C$ 由输入给出。

虽然这个任务对 cki86201 来说很简单，但他现在必须去玩《守望先锋》。请找出以最小成本重新排列集装箱的方法。

输入格式

第一行给出两个整数 $N, C$。($1 \le N \le 500, 0 \le C \le 1000$)

下一行给出一个长度为 $N$ 的字符串，由字符 '1' 和 '2' 组成。这表示仓库中当前排列的集装箱容量。

再下一行给出一个长度为 $N$ 的字符串，由字符 '1' 和 '2' 组成。这表示仓库中期望排列的集装箱容量。

保证两个字符串中 '1' 的数量相等，'2' 的数量也相等。

输出格式

第一行输出一个整数 $K$，表示你使用机器的次数。

接下来的 $K$ 行，每行输出两个整数 $i, j$ ($1 \le i < j \le N, j - i \le 2$)，表示你使用机器反转了当前状态下第 $i, i+1, \dots, j$ 个集装箱。

如果你的方案有效（即模拟该操作序列后能得到期望的排列）且使用了最小可能的成本，则你的答案将被视为正确。

样例

样例输入 1

5 2
11221
21112

样例输出 1

2
1 3
4 5

样例输入 2

7 0
2212121
1212122

样例输出 2

4
6 7
4 6
2 4
1 2

样例输入 3

7 2
2212121
1212122

样例输出 3

3
1 3
3 5
5 7