P15620 [ICPC 2022 Jakarta R] Substring Sort

In this problem, all strings are one-based indexed. Let $s_i$ be the $i^{th}$ character of a string $s$. Let $s_{l..r}$ be a substring of $s$ with the characters $s_l s_{l+1} \cdots s_r$. You are given three strings each of length $N$: $A$, $B$, and $C$. You are asked to simulate $Q$ queries according to the given order. For each query, you are given two integers $l$ and $r$ as parameters, and must perform the following procedures: 1. Copy substrings $A_{l..r}$, $B_{l..r}$, and $C_{l..r}$. Let $x$, $y$ and $z$ be the copied substrings. 2. Sort $[x, y, z]$ in lexicographical order. Let $[x', y', z']$ be the sorted results. 3. Replace substring $A_{l..r}$ with $x'$, substring $B_{l..r}$ with $y'$ and substring $C_{l..r}$ with $z'$ respectively. Determine the value of $A$, $B$, and $C$ after all queries.

Input begins with two integers $N$ $Q$ ($1 \leq N \leq 100\,000$; $1 \leq Q \leq 100\,000$) representing the length of the given strings and the number of queries. Each of the next $3$ lines contains a string of length $N$. The first, second, and third lines contain $A$, $B$, and $C$ respectively. The strings consist of lowercase characters. Each of the next $Q$ lines contains two integers $l$ $r$ ($1 \leq l \leq r \leq N$) representing the parameters of each query.

The output consists of $3$ lines. In each line, output the final value of $A$, $B$ and $C$ after all queries in that order.

#### Explanation for the sample input/output #1 In the first query, the value of $x$, $y$, and $z$ are cpc, iaj, art respectively. After sorting those strings, the value of $x'$, $y'$, and $z'$ becomes art, cpc, iaj. At the end of the first query, the value of $A$, $B$, and $C$ are iarta, scpca and kiaja. During the second query, the value of $x$, $y$, and $z$ are iarta, scpca, kiaja respectively. After sorting those strings, the value of $x'$, $y'$, and $z'$ becomes iarta, scpca, kiaja. At the end of the second query, the value of $A$, $B$, and $C$ are iarta, kiaja and scpca. Therefore the final value of $A$, $B$, $C$ are iarta, kiaja and scpca respectively.