#215682. [ICPC 2022 Jakarta R] Substring Sort

In this problem, all strings are one-based indexed. Let be the character of a string . Let be a substring of with the characters .

You are given three strings each of length : , , and . You are asked to simulate queries according to the given order.

For each query, you are given two integers and as parameters, and must perform the following procedures:

1. Copy substrings , , and . Let , and be the copied substrings.
2. Sort in lexicographical order. Let be the sorted results.
3. Replace substring with , substring with and substring with respectively.

Determine the value of , , and after all queries.

Input begins with two integers (; ) representing the length of the given strings and the number of queries. Each of the next lines contains a string of length . The first, second, and third lines contain , , and respectively. The strings consist of lowercase characters. Each of the next lines contains two integers () representing the parameters of each query.

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

样例输入 1

5 2
icpca
siaja
karta
2 4
1 5

样例输出 1

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

Explanation for the sample input/output #1

In the first query, the value of , , and are cpc, iaj, art respectively. After sorting those strings, the value of , , and becomes art, cpc, iaj. At the end of the first query, the value of , , and are iarta, scpca and kiaja.

During the second query, the value of , , and are iarta, scpca, kiaja respectively. After sorting those strings, the value of , , and becomes iarta, scpca, kiaja. At the end of the second query, the value of , , and are iarta, kiaja and scpca.

Therefore the final value of , , are iarta, kiaja and scpca respectively.