Substring Sort

In this problem, all strings are indexed from 1. $s_i$ is the $i$th character of string $s$, and $s_{l..r}$ is the substring $s_l s_{l+1} \cdots s_r$.

You are given three strings $A$, $B$, and $C$, each of length $N$. You must process $Q$ queries in order. Each query gives two integers $l$ and $r$, and you perform these steps:

1. Copy the substrings $A_{l..r}$, $B_{l..r}$, and $C_{l..r}$. Call the copies $x$, $y$, and $z$.
2. Sort $[x, y, z]$ in lexicographical order. Call the sorted result $[x', y', z']$.
3. Replace $A_{l..r}$ with $x'$, $B_{l..r}$ with $y'$, and $C_{l..r}$ with $z'$.

Find the final values of $A$, $B$, and $C$ after all queries.

The first line has two integers $N$ and $Q$ ($1 \le N \le 100\,000$, $1 \le Q \le 100\,000$). The next three lines contain the strings $A$, $B$, and $C$, each of length $N$, made of lowercase letters. Each of the next $Q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le N$).

Print three lines with the final values of $A$, $B$, and $C$, in that order.