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 ≤ n < m ≤ 2·10^5 , n+m ≤ x ≤ 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 ≤ p ≤ x)$ and a character $t (t ∈ \{P, 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· · \n · \n · \n · \n · \n · \n · \n
2 3\n \n
1000000000 2 4 1 P 6 H 31415926 H 999999998 H 999999999 H 1000000000 P· · \n · \n · \n · \n · \n · \n · \n
4 1\n \n
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.