부분 문자열 정렬

이 문제에서 모든 문자열의 인덱스는 1부터 시작한다. $s_i$는 문자열 $s$의 $i$번째 문자이고, $s_{l..r}$은 $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. $A_{l..r}$을 $x'$으로, $B_{l..r}$을 $y'$으로, $C_{l..r}$을 $z'$으로 바꾼다.

모든 쿼리를 처리한 뒤 $A$, $B$, $C$의 최종 값을 구하라.

첫 줄에 정수 $N$과 $Q$가 주어진다 ($1 \le N \le 100\,000$, $1 \le Q \le 100\,000$). 다음 세 줄에는 각각 길이 $N$의 소문자 문자열 $A$, $B$, $C$가 주어진다. 이어서 $Q$개의 줄에 정수 $l$과 $r$ ($1 \le l \le r \le N$)이 주어진다.

$A$, $B$, $C$의 최종 값을 이 순서대로 세 줄에 출력한다.