Note

This is the problem for Day 8 of Advent Calendar Contest 2019.
Today is the day of the second qualifying round of JOI2019/2020.
We wish all contestants the best of luck.

Problem Statement

Chairman Y has recently been absorbed in arranging yuki manju on plates.
There are manju with $3$ kinds of stamps among yuki manju: Y, K, and C.
Chairman Y arranges manju on $N$ plates, numbered $1,2,...,N$ from the left, by performing $M$ operations under the following rules.

• In the $i(1 \le i \le M)$-th operation, two integers $L_i$ and $R_i$ and a manju type $T_i$ are given. This means placing a manju stamped with $T_i$ on each of the $L_i,L_i+1,...,R_i$-th plates from the left.
• However, in each operation, if a manju has already been placed on a plate, no new manju is placed on that plate.

Input

$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)$ is one of Y, K, or C.

Output

Output on $1$ line, separated by spaces, the total numbers of manju stamped with Y, K, and C placed on the plates, in this order, followed by a newline at the end.

Subtasks

This problem has several subtasks. You earn no contest points unless you solve it completely, but you may use them as a reference for the level of your solution.

1. $N,M \le 1000$. This subtask is cleared by passing all cases whose test case names contain Small or Sample.
2. No additional constraints. You must pass all test cases.

Sample

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