Frequencies

On an $n \cdot n$ matrix, initially empty, you perform $m$ operations. Each operation can be of the following two kinds:

• Horizontal$(l, r, x)$: All cells in rows $l, l + 1, \dots, r$ are set to value $x$
• Vertical$(l, r, x)$: All cells in columns $l, l + 1, \dots, r$ are set to value $x$

After executing all operations, report how many times do the least and most frequent elements occur in the matrix.

Input

The first line contains the size of the matrix $n$, and the number of operations $m$.

Each of the next $m$ lines describe one operation.

The $i^{th}$ operation is described by 4 values $t_i, l_i, r_i, x_i$, where $t_i$ is a character that describes the kind of the $i^{th}$ operation (either H for horizontal or V for vertical) and $l_i, r_i, x_i$ describe the $i^{th}$ operation.

Output

The output consists of a single line that contains the frequency of the element that appears least often $fr_{min}$ and the frequency of the element that appears most often in the matrix $fr_{max}$ after carrying out the $m$ operations.

Constraints

• $1 \leq n \leq 1 \ 000 \ 000$
• $t_i \in \{$ H, V$\}$
• $1 \leq l_i \leq r_i \leq n$
• $1 \leq m \leq 200 \ 000$
• $1 \leq x_i \leq 100 \ 000$

Subtasks

• For 20 points: $1 \leq n \leq 1 \ 000$, $1 \leq m \leq 100$, $1 \leq x_i \leq 40$
• For another 20 points: $1 \leq n \leq 2 \ 000$, $1 \leq n^2 \cdot m \leq 1 \ 000 \ 000 \ 000$
• For another 20 points: $1 \leq n \leq 6 \ 000$, $1 \leq m \leq 100 \ 000$
• For another 20 points: $1 \leq n \leq 200 \ 000$
• For another 20 points: No further restrictions

Note: The tests for this task are scored individually!

Example 1

stdin

5 4
H 1 4 2
H 3 5 1
V 2 2 1
H 3 4 3

stdout

7 10

Example 2

stdin

6 5
V 5 5 3
H 4 5 4
V 1 6 3
V 1 2 2
V 4 4 2

stdout

18 18

Example 3

stdin

6 5
H 3 4 2
V 4 5 1
V 4 6 2
H 5 6 2
H 5 6 4

stdout

12 18

Example 4

stdin

8 8
H 4 8 3
H 2 3 3
V 5 7 3
V 4 5 2
H 1 6 2
V 7 8 2
V 5 6 2
H 2 4 4

stdout

6 34

Explanation

In the first example, after applying all the operations, the matrix looks as follows:

$2 \ 1 \ 2 \ 2 \ 2$
$2 \ 1 \ 2 \ 2 \ 2$
$3 \ 3 \ 3 \ 3 \ 3$
$3 \ 3 \ 3 \ 3 \ 3$
$1 \ 1 \ 1 \ 1 \ 1$

The least frequent element is $1$ with a frequency of $7$, and the most frequent element is $3$ with a frequency of $10$.

In the third example, after applying all the operations, the matrix looks as follows:

$\_ \ \_ \ \_ \ 2 \ 2 \ 2$
$\_ \ \_ \ \_ \ 2 \ 2 \ 2$
$2 \ 2 \ 2 \ 2 \ 2 \ 2$
$2 \ 2 \ 2 \ 2 \ 2 \ 2$
$4 \ 4 \ 4 \ 4 \ 4 \ 4$
$4 \ 4 \ 4 \ 4 \ 4 \ 4$

The least frequent element is $4$ with a frequency of $12$ and the most frequent element is $2$ with a frequency of $18$.