002 - String Replacement

時間制限 2 秒 / メモリ制限 64 MB / 得点 200 / x 55 /


TLE
2sec
MLE
64MB
得点
200

問題

ei1903はもけちゃんから長さ $L$ の * のみから成る文字列 $S$ を貰った。
しかし、全ての文字が * というのはつまらないので以下のような操作を $Q$ 回行うことにした。

  • $i$ $(1 \leq i \leq Q)$ 回目の操作で $S$ の $l_i$ 文字目から $r_i$ 文字目までを文字 $c_i$ で置き換える。
$Q$ 回の操作を終えた後の $S$ を出力せよ。

入力

入力は以下の形式で標準入力から与えられる。
$L$ $Q$
$l_1$ $r_1$ $c_1$
$l_2$ $r_2$ $c_2$
$\vdots$
$l_Q$ $r_Q$ $c_Q$

出力

$Q$ 回の操作を終えた後の $S$ を出力せよ。
出力の末尾には改行を入れること。

制約

  • $1 \leq L \leq 10^3$
  • $0 \leq Q \leq 10^3$
  • $1 \leq l_i \leq r_i \leq L$
  • $c_i$ は英小文字である。

入出力例

入力例1

10 5
2 4 a
9 10 t
3 6 x
8 8 c
5 10 o

出力例1

*axxoooooo

$S$ に対して以下のように操作が行われる。

  • $(i = 1)$ $S =$ *aaa******
  • $(i = 2)$ $S =$ *aaa****tt
  • $(i = 3)$ $S =$ *axxxx**tt
  • $(i = 4)$ $S =$ *axxxx*ctt
  • $(i = 5)$ $S =$ *axxoooooo


入力例2

5 0

出力例2

*****

操作が一度も行われない場合もある。


入力例3

30 10
7 23 x
1 3 o
8 13 b
8 10 d
30 30 t
27 29 p
2 10 n
16 19 l
11 13 f
15 15 e

出力例3

onnnnnnnnnfffxellllxxxx***pppt