String Crossing

Time Limit : 3 sec, Memory Limit : 262142 KB

String Crossing

Problem

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

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

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

a  - -> bcd
    X
ef - -> gh

S1="agh",S2="efbcd"となる。

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

Input

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

N Q
S1
S2
...
SN
query1
query2
...
queryQ
queryは次のいずれかである。
1 a b c d

or

2 a b c

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • N個の文字列の長さの合計は2×106を越えない。
  • 文字列Siは全て英小文字であることが保証される。
  • クエリの種類が1のとき
    • ac
    • 1 ≤ b ≤ |Sa|
    • 1 ≤ d ≤ |Sc|
  • クエリの種類が2のとき
    • 1 ≤ b ≤ |Sa|
    • cは英小文字であることが保証される。

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

Output

各クエリを処理した後の文字列をS1からSNまで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

Source: Aizu Competitive Programming Camp 2015 Day2 , Japan, 2015-09-22