問題
とあるアナウンサーがニュース速報の原稿を読み上げようとしたところ、原稿の一行目と二行目が混ざって変な読み上げ方をしてしまった。
まず原稿の1行目の内容 $a$ と2行目の内容 $b$ が文字数($n$,$m$)つきで与えられる。
そのあと $q$ 個のクエリが与えられる。 $i$ 番目のクエリでは、$s_i$ 番目の行の $l_i$ 文字目から $r_i$ 文字目までを記録せよ。
最後に、記録した文字列をクエリ順に並べて一行で出力せよ。
入力
入力は以下の形式で標準入力から与えられる。
$n$ $m$ $a$ $b$ $q$ $query_1$ $query_2$ ... $query_q$各クエリは次のように与えられる。
$s_i$ $l_i$ $r_i$
出力
記録した文字列をクエリ順に並べて一行で出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $a,b$ は全て半角英字
- $1 \leq l_i \le r_i \le n,m \leq 10^{5}$
- $s_i = 1,2$
- $1 \leq q \leq 10^{5}$
- 答えの文字列は $10^{5}$ 文字以内
入出力例
入力例1
5 10 paris paralympic 7 1 1 4 2 3 4 2 1 3 1 1 4 2 3 4 1 3 3 2 1 10
出力例1
pariraparparirarparalympic
例えば1つ目のクエリでは、1行目の1~4文字目である"pari"が記録される文字列となる。
入力例2
7 8 maitake guruguru 8 1 1 7 1 1 7 2 1 8 2 1 8 1 1 7 1 1 7 2 1 8 2 1 8
出力例2
maitakemaitakegurugurugurugurumaitakemaitakeguruguruguruguru