#P18135. Puzzle II

Puzzle II

Puzzle II

有两个长度为 nn 的循环球序列,球为白色 B 或黑色 C。两个序列合起来恰好有 nn 个白球和 nn 个黑球。

一次操作可以选择第一个序列中长度为 kk 的循环区间,以及第二个序列中长度为 kk 的循环区间,并交换这两个区间。

请在不超过 nn 次操作内,使两个序列都变成单色,即每个序列中的所有球颜色相同。可以证明总是有解。

输入格式

第一行包含 n,kn,k,满足 2≤n≤3000002\le n\le300000、1≤k<n1\le k<n。

接下来两行分别为只含 B、C 的长度为 nn 的字符串。两个字符串合计恰有 nn 个 B 和 nn 个 C。

输出格式

第一行输出操作次数 rr,满足 0≤r≤n0\le r\le n。

接下来 rr 行,每行输出两个整数 ci,dic_i,d_i,分别表示两个序列中被交换循环区间的起点。

样例

6 3
BCCBCC
BBCBBC

一种合法输出为:

4
1 3
1 4
4 1
4 2

操作示意:

Puzzle II