Sắp xếp xâu con

Cho ba xâu \(A, B, C\), thực hiện \(q\) truy vấn trên ba xâu này như sau:

• Mỗi truy vấn gồm hai số \(l, r\)
• Gọi \(x = A_{l},A_{l+1}...A_{r}\) ; \(y = B_{l}B_{l+1}...B_{r}\); \(z = C_{l}C_{l+1}...C_{r}\)
• Sắp xếp ba xâu \(x, y, z\) thành \(x′,y′,z′\)
• Gán lại các kí tự của xâu \(A\) từ \(l\) đến \(r\) thành \(x′\) , gán các kí tự của xâu \(B\) từ \(l\) đến \(r\) thành \(y′\) , gán các kí tự của xâu \(C\) từ \(l\) đến \(r\) thành \(z′\).

Hãy đưa ra ba xâu \(A, B, C\) sau khi thực hiện xong \(q\) truy vấn.

Input

Dòng đầu chứa số \(n, q\) \((1 \leq n,q \leq 10^5)\)

Ba dòng tiếp theo chứa ba xâu \(A,B,C\) có cùng độ dài chỉ chứa các kí tự thường.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số \(l,r\) \((1 \leq l \leq r \leq n)\) mô tả các truy vấn.

Output

Đưa ra ba xâu trên ba dòng sau khi thực hiện xong các truy vấn.

Example

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

Scoring

\(30\%\) số điểm có \(n, q \leq 10^3\).

\(30\%\) số điểm có \(n, q \leq 10^4\).

\(40\%\) số điểm không có ràng buộc gì thêm.