집 철거

시간 제한1초메모리 제한2048 MB

요약

원형 위에 놓인 사람과 집의 위치가 주어질 때, 일부 집을 없앤 뒤 최소 이동 거리를 구하고 그 최솟값을 이루는 제거 집합의 개수를 셉니다.

난이도: 어려움10점 중 9점
유형: 조합론, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

Circleland라는 나라에 둘레를 따라 같은 간격으로 점이 놓인 원이 있다. 인접한 두 점 사이의 거리는 $1$ 이다.

각 점에는 사람, 빈 집, 또는 아무것도 없다. 각 사람은 서로 다른 집으로 걸어가려고 하며, 집 하나에는 최대 한 명의 사람만 들어갈 수 있다. 사람은 원의 둘레를 따라서만 걸을 수 있고 원을 가로질러 갈 수 없다.

지금은 사람보다 집이 많으므로 일부 집을 부수려고 한다. 부술 집들의 집합을 $S$ 라 하자. $f(S)$ 는 부수지 않은 집 중 서로 다른 집으로 모든 사람을 옮기는 데 필요한 최소 총 이동 거리이다.

$f(S)$ 의 최솟값을 구하고, 이 최솟값을 달성하는 집합 $S$ 의 개수를 구하라. 개수가 클 수 있으므로 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

입력

첫 줄에 세 정수 $x$ , $n$ , $m$ 이 주어진다 ( $1 \leq n < m \leq 2 \cdot 10^5, n+m \leq x \leq 10^9$ ). $x$ 는 원 둘레의 점 개수, $n$ 은 사람 수, $m$ 은 집 수이다. 점에는 1부터 $x$ 까지 번호가 붙어 있으며, 점 $x$ 는 점 1과 인접한다.

다음 $n+m$ 개의 줄에는 각각 정수 $p$ ( $1 \le p \le x$ )와 문자 $t$ ( $t \in \{$ P,H $\}$ )가 주어진다. $p$ 는 사람 또는 집의 위치이고, $t$ 는 그 점의 종류로 P는 사람, H는 집이다. 모든 위치는 서로 다르며 증가하는 순서로 주어진다.

출력

첫 줄에 $f(S)$ 의 가능한 최솟값을 출력한다. 둘째 줄에는 이 최솟값을 달성하는 집합 $S$ 의 개수를 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

힌트

첫 번째 예제에서 최소 총 이동 거리는 2이다. 위치 2와 5, 4와 5, 또는 5와 6의 집을 부수면 이 값을 얻는다.

두 번째 예제에서는 위치 6과 31415926의 집을 부수면 최소 총 이동 거리 4가 된다. 같은 최솟값을 얻는 방법이 여러 가지 있더라도, 부순 집의 집합이 같다면 한 번만 센다.

예제2

예제 1
입력
```
6 2 4
1 P
2 H
3 P
4 H
5 H
6 H
```
예상 출력
```
2
3
```

예제 2

입력

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

예상 출력

4
1