在本题中，所有字符串均采用 1-based 索引。令 $s_i$ 为字符串 $s$ 的第 $i$ 个字符。令 $s_{l..r}$ 为字符串 $s$ 中由字符 $s_l s_{l+1} \dots s_r$ 组成的子串。
给定三个长度均为 $N$ 的字符串：$A$、$B$ 和 $C$。你需要按照给定的顺序模拟 $Q$ 次查询。
对于每次查询，给定两个整数 $l$ 和 $r$ 作为参数，必须执行以下步骤：
- 复制子串 $A_{l..r}$、$B_{l..r}$ 和 $C_{l..r}$。令 $x$、$y$ 和 $z$ 为复制得到的子串。
- 将 $[x, y, z]$ 按字典序排序。令排序后的结果为 $[x', y', z']$。
- 分别用 $x'$ 替换子串 $A_{l..r}$，用 $y'$ 替换子串 $B_{l..r}$，用 $z'$ 替换子串 $C_{l..r}$。
确定所有查询结束后 $A$、$B$ 和 $C$ 的值。
输入格式
输入的第一行包含两个整数 $N$ 和 $Q$ ($1 \le N \le 100\,000$; $1 \le Q \le 100\,000$)，分别表示给定字符串的长度和查询次数。接下来的 3 行每行包含一个长度为 $N$ 的字符串。第一、二、三行分别包含 $A$、$B$ 和 $C$。字符串由小写字母组成。接下来的 $Q$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le N$)，表示每次查询的参数。
输出格式
输出共 3 行。每行依次输出所有查询结束后 $A$、$B$ 和 $C$ 的最终值。
样例
样例输入 1
5 2 icpca siaja karta 2 4 1 5
样例输出 1
iarta kiaja scpca
说明 1
在第一次查询中，$x$、$y$ 和 $z$ 的值分别为 cpc、iaj 和 art。对这些字符串排序后，$x'$、$y'$ 和 $z'$ 的值变为 art、cpc 和 iaj。第一次查询结束时，$A$、$B$ 和 $C$ 的值分别为 iarta、scpca 和 kiaja。
在第二次查询中，$x$、$y$ 和 $z$ 的值分别为 iar、scp 和 kia。对这些字符串排序后，$x'$、$y'$ 和 $z'$ 的值变为 iar、kia 和 scp。第二次查询结束时，$A$、$B$ 和 $C$ 的值分别为 iarta、kiaja 和 scpca。
因此，$A$、$B$ 和 $C$ 的最终值分别为 iarta、kiaja 和 scpca。
样例输入 2
6 6 aabbcc bcacab cbcaba 1 1 2 2 3 3 4 4 5 5 6 6
样例输出 2
aaaaaa bbbbbb cccccc
样例输入 3
3 1 aba aab aac 1 3
样例输出 3
aab aac aba