E - EGFクエリ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

整数 N,Q と英大文字からなる長さ N の文字列 S が与えられます。

Q 個のクエリが与えられるので、これらのクエリを順に処理した際の最終的な S を求めてください。

各クエリは以下の形式で与えられます。

  • タイプ 1：1 x の形式で与えられる。 S の x 文字目と x+1 文字目を入れ替える。
  • タイプ 2：2 x の形式で与えられる。 S の先頭 x 文字を削除する。

制約

  • 1\le N\le 10^6
  • 1\le Q\le 10^6
  • N,Q は整数
  • S は英大文字からなる長さ N の文字列
  • タイプ 1 のクエリについて、そのクエリ時点での S の長さを L としたとき 1\le x\le L - 1
  • タイプ 2 のクエリについて、そのクエリ時点での S の長さを L としたとき 1\le x\le L

入力

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

N Q
S
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 x

2 x

出力

クエリを順に処理した際の最終的な S を出力せよ。

入力例 1

7 3
ABCDEFG
1 1
2 4
1 2

出力例 1

EGF

各クエリを処理していくと S は以下のようになります：

  • S の 1 文字目と 2 文字目を入れ替える。 S= BACDEFG となる。
  • S の先頭 4 文字を削除する。 S= EFG となる。
  • S の 2 文字目と 3 文字目を入れ替える。 S= EGF となる。

最終的な S は EGF となるので、 EGF を出力してください。

入力例 2

7 3
ATCODER
1 1
1 6
2 7

出力例 2



最終的な S が空文字列となる場合もあります。













入力例 3
16 6
ENGINEERGUILDFES
1 3
2 5
1 4
1 3
2 1
1 4












出力例 3
EURIGLDFES