题目描述

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.

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

提示

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.