题目描述

在圆环之国，有一个圆周上均匀分布着若干点。相邻两点之间的距离为 $1$。

圆周上的点上有人和房屋。每个点上要么有一个人，要么有一个空房子，要么什么都没有。每个人都想走到一个不同的房屋。每个房屋最多只能容纳一个人。人们只能沿着圆周行走，不能穿过圆内。

目前，房屋的数量多于人的数量，因此你想拆除一些房屋。假设你拆除了一组房屋 $S$。记 $f(S)$ 为让每个人走到一个不同的未被拆除的房屋所需的最小总行走距离。

请计算 $f(S)$ 的最小可能值，以及有多少组房屋集合 $S$ 能达到这个最小值。由于 $S$ 的数量可能很大，请输出其对 $998,244,353$ 取模的结果。

输入格式

输入的第一行包含三个整数 $x$、$n$ 和 $m$（$1 \le n < m \le 2 \cdot 10^5$，$n + m \le x \le 10^9$），其中 $x$ 是圆周上的点数，$n$ 是人数，$m$ 是房屋数。点的编号为 $1$ 到 $x$，且点 $x$ 与点 $1$ 相邻。

接下来的 $n + m$ 行，每行包含两个标记：一个整数 $p$（$1 \le p \le x$）和一个字符 $t$（$t \in \{\text{P}, \text{H}\}$），其中 $p$ 表示人或房屋的位置，$t$ 表示该点的类型（P 代表人，H 代表房屋）。所有位置互不相同，并且位置按递增顺序给出。

输出格式

输出两行。第一行输出 $f(S)$ 的最小可能值。第二行输出达到该最小值的集合 $S$ 的数量，对 $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

提示

样例解释

对于第一个样例，最小总行走距离为 $2$。我们可以拆除的房屋集合有 $\{2,5\}$、$\{4,5\}$ 或 $\{5,6\}$。

对于第二个样例，我们可以拆除的房屋集合为 $\{6,31415926\}$，最小总行走距离为 $4$。请注意，即使有多种方式达到最小行走距离，由于拆除的房屋集合相同，只被计数一次。

翻译由 DeepSeek V3.2 完成