メモ

これはAdvent Calendar Contest 2019の8日目用の問題である．
本日はJOI2019/2020の二次予選当日である．
選手諸君の健闘を祈る．

問題文

Y理事長は，最近yuki饅頭を皿に並べることに夢中である．
yuki饅頭には，Y，K，Cの$3$種類の刻印の入った饅頭が存在する．
Y理事長は，以下のルールのもと，左から順に$1,2,...,N$の番号のついた$N$枚の皿に$M$回の操作を施して饅頭を並べていく．

• $i(1 \le i \le M)$回目の操作では，2つの整数$L_i$と$R_i$と饅頭の種類$T_i$が与えられる．これは，左から$L_i,L_i+1,...,R_i$番目の皿に$T_i$の刻印の入った饅頭を置くことを表す．
• 但し，各操作について，ある皿にすでに饅頭が置かれている場合，その皿には饅頭を新たに置くことはしない．

入力

$N\ M$
$L_1\ R_1\ T_1$
$L_2\ R_2\ T_2$
$\vdots$
$L_M\ R_M\ T_M$

• $1 \le N,M \le 200000 (= 2 \times 10^5)$
• $1 \le L_i \le R_i \le N(1 \le i \le M)$
• $T_i(1 \le i \le M)$はY，K，Cのいずれかである．

出力

Y，K，Cの刻印の入った饅頭が全体でいくつ皿に置かれたかをこの順に空白区切りで$1$行に出力し，最後に改行せよ．

小課題

この問題にはいくつか小課題が設定されている．完解でなければコンテストでの得点は得られないが，自分の解答のレベルの参考にするとよいだろう．

1. $N,M \le 1000$である．SmallまたはSampleがテストケース名に含まれるようなケースをすべて通過すればこの小課題は認められる．
2. 追加の制約はない．すべてのテストケースに通過する必要がある．

サンプル

5 2
1 3 Y
3 5 C

3 0 2

8 7
3 6 Y
1 5 C
1 1 Y
5 7 C
3 4 Y
5 6 K
4 7 Y

4 0 3