# Frequencies

Time limit: 0.15s Memory limit: 256MB Input: Output:

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$

• 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$.