String Crossing

Problem

N個の文字列{ S₁, S₂, ..., S_N } が与えられる。 続いてQ個のクエリが与えられる。 クエリの種類は以下の2つである。

1. a,b,c,dが入力されS_a の b文字目からの substring を S_c の d-1文字までの substring の後に繋げる。これを新しいS_cとする。 元のS_c の d文字目からの substring を S_a の b-1文字までの substring の後に繋げる。これを新しいS_aとする。
2. a,b,cが入力され S_a の b文字目を c に変更する。

例えばS₁="abcd",S₂="efgh"があり クエリの種類が1でa=1,b=2,c=2,d=3のとき

a  - -> bcd
    X
ef - -> gh

S₁="agh",S₂="efbcd"となる。

全てのクエリを処理した後の文字列S₁からS_Nを全て出力せよ。

Input

入力は以下の形式で与えられる。

N Q
S1
S2
...
SN
query1
query2
...
queryQ

1 a b c d

or

2 a b c

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• N個の文字列の長さの合計は2×10⁶を越えない。
• 文字列S_iは全て英小文字であることが保証される。
• クエリの種類が1のとき
  • a ≠ c
  • 1 ≤ b ≤ |S_a|
  • 1 ≤ d ≤ |S_c|
• クエリの種類が2のとき
  • 1 ≤ b ≤ |S_a|
  • cは英小文字であることが保証される。

高速な入出力を推奨する。

Output

各クエリを処理した後の文字列をS₁からS_Nまで1行ずつ出力せよ。

S1
S2
...
SN

Sample Input 1

2 1
abcd
efgh
1 1 2 2 3

Sample Output 1

agh
efbcd

Sample Input 2

2 3
abcd
efgh
1 1 2 2 3
2 1 3 x
2 2 4 x

Sample Output 2

agx
efbxd

Sample Input 3

10 10
sjcvpauokb
fmeaowomscy
sepeqqfcosrjmonfsv
zapc
aromazjzqoeiqswvcaf
clifpa
dusudcz
qeqdzdtdzlkhc
gkpsjvdvadmf
xrtyxnkolluagwxp
1 4 4 6 3
1 7 1 8 1
2 2 6 o
1 4 4 3 7
2 1 2 i
1 6 3 3 2
1 6 5 1 9
2 10 9 j
1 2 2 7 3
2 3 2 b

Sample Output 3

sicvpauoeqqifpa
fqdzdtdzlkhc
sb
zapfcosrjmonfsv
aromazjzqoeiqswvcaf
clepkb
qemeaooomscy
dusudcz
gkpsjvdvadmf
xrtyxnkojluagwxp