Awaiting one last dance

本题的时间限制为10s

题目描述

lhy 和 pzr 正在玩无聊的小游戏. lhy 和 pzr 会各自构造一个长度为 n 的字符串 $s_1,s_2$, zys 看到以后想要通过不超过 n 次操作使得 $s_1=s_2$. 操作如下：

• 1 l r, 令$s_1[l+i]=s_1[r-i],~0\le i \le r-l$.
• 2 l r, 令$s_2[l+i]=s_2[r-i],~0\le i \le r-l$.

如果有多种方式满足题意, 输出任何一个都可以. 如果不能在 $n$ 次操作内完成, 输出 -1.

注意：字符串从 1 开始编号, 要求$1 \le l < r \le |s_i|$.

数据格式

输入

第一行, 一个正整数 n.

第二行, 长度为 n 的字符串 $s_1$.

第三行, 长度为 n 的字符串 $s_2$.

输出

第一行, 一个正整数 k, 表示需要使用的操作数.

接下来 k 行, 每行三个整数表示一次操作.

如果不能完成则直接输出一行-1.

样例

输入

18
FreshmanContestNNU
FreshmanNNUContest

输出

6
1 1 18
1 1 3
1 4 18
2 1 11
2 1 3
2 4 11

样例解释

两个字符串最后都会变成 NNUFreshmanContest.

数据范围及约定

$n \le 10^5$. 字符串里面的字符只有数字和英文大小写共计$10+26+26$种.