说明

在本问题中，所有字符串的下标均从 $1$ 开始。令 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符。令 $s_{l..r}$ 表示 $s$ 的一个子串，包含字符 $s_l s_{l+1} \cdots s_r$。

给定三个长度均为 $N$ 的字符串：$A$、$B$ 和 $C$。要求你按照给定的顺序模拟 $Q$ 次查询。

对于每次查询，你会得到两个整数 $l$ 和 $r$ 作为参数，并必须执行以下步骤：

1. 复制子串 $A_{l..r}$、$B_{l..r}$ 和 $C_{l..r}$。令 $x$、$y$ 和 $z$ 分别为复制得到的子串。
2. 将 $[x, y, z]$ 按字典序排序。令 $[x', y', z']$ 为排序后的结果。
3. 分别用 $x'$ 替换子串 $A_{l..r}$，用 $y'$ 替换子串 $B_{l..r}$，用 $z'$ 替换子串 $C_{l..r}$。

请确定所有查询完成后 $A$、$B$ 和 $C$ 的值。

输入格式

输入以两个整数 $N$ $Q$（$1 \leq N \leq 100\,000$；$1 \leq Q \leq 100\,000$）开始，分别表示给定字符串的长度和查询次数。接下来的 $3$ 行，每行包含一个长度为 $N$ 的字符串。第一行、第二行和第三行分别包含 $A$、$B$ 和 $C$。字符串仅由小写字母组成。接下来的 $Q$ 行，每行包含两个整数 $l$ $r$（$1 \leq l \leq r \leq N$），表示每次查询的参数。

输出格式

输出包含 $3$ 行。每行按顺序输出所有查询完成后 $A$、$B$ 和 $C$ 的最终值。

5 2
icpca
siaja
karta
2 4
1 5

iarta
kiaja
scpca

6 6
aabbcc
bcacab
cbcaba
1 1
2 2
3 3
4 4
5 5
6 6

aaaaaa
bbbbbb
cccccc

3 1
aba
aab
aac
1 3

aab
aac
aba

提示

样例输入/输出 #1 的解释

在第一次查询中，$x$、$y$、$z$ 的值分别为 cpc、iaj、art。将这些字符串排序后，$x'$、$y'$、$z'$ 的值变为 art、cpc、iaj。第一次查询结束时，$A$、$B$、$C$ 的值分别为 iarta、scpca 和 kiaja。

在第二次查询中，$x$、$y$、$z$ 的值分别为 iarta、scpca、kiaja。将这些字符串排序后，$x'$、$y'$、$z'$ 的值变为 iarta、scpca、kiaja。第二次查询结束时，$A$、$B$、$C$ 的值分别为 iarta、kiaja 和 scpca。

因此，$A$、$B$、$C$ 的最终值分别为 iarta、kiaja 和 scpca。

翻译由 DeepSeek 完成