题目描述

In the land of Circleland, there is a circle that has equally spaced points around its circumference. The distance between any two adjacent points is $1$.

There are people and houses on the circle’s points. Each point contains a person, an empty house, or nothing at all. Each person would like to walk to a different house. Each house can contain at most one person. People can only walk along the circumference of the circle; they cannot cut across.

Currently, there are more houses than people, so you’d like to destroy some of the houses. Suppose you destroy a set of houses $S$. Let $f(S)$ be the minimum total amount of walking needed to get each person to a different non-destroyed house.

Compute the minimum value of $f(S)$, compute how many sets of houses $S$ achieve this minimum value. Since the number of sets $S$ can be large, output it modulo $998,244,353$.

输入格式

The first line of input contains three integers $x$, $n$, and $m$ ($1 \le n < m \le 2 \cdot 10^5$, $n + m \le x \le 10^9$), where $x$ is the number of points around the circle, $n$ is the number of people, and $m$ is the number of houses. The points are labeled $1$ to $x$, and point $x$ is adjacent to point $1$.

The next $n + m$ lines each contain two tokens, an integer $p$ ($1 \le p \le x$) and a character $t$ ($t \in \{\text{P}, \text{H}\}$), where $p$ denotes the position of a person or house, and $t$ denotes the type of the point, either P for person or H for house. All positions are distinct, and the positions will be given in increasing order.

输出格式

Output two lines. On the first line output the minimum possible value of $f(S)$. On the second line output the number of sets $S$ that achieve this minimum value, modulo $998,244,353$.

6 2 4
1 P
2 H
3 P
4 H
5 H
6 H

2
3

1000000000 2 4
1 P
6 H
31415926 H
999999998 H
999999999 H
1000000000 P

4
1

提示

Sample Explanation

For the first sample, the minimum total walking distance is $2$. We can destroy the set of houses at $\{2,5\}$, $\{4,5\}$ or $\{5,6\}$.

For the second sample, we can destroy the set of houses at $\{6,31415926\}$ for a minimum total walking distance of $4$. Note that even though the minimum walking distance can be achieved in multiple ways, it is only counted once since the set of destroyed houses is the same.