$n$개의 정점을 가진 가중치 무방향 그래프가 있으며, 정점은 $\{0, 1, \cdots, n - 1\}$로 번호가 매겨져 있습니다. 처음에 $b$개의 간선이 있으며, $i$번째 간선은 $u_i$와 $v_i$를 연결하고 가중치는 $w_i$입니다.

이어서 $a$번의 연산을 순차적으로 수행합니다. $i$번째 연산에서는 번호 차이가 $d_i$인 모든 정점 쌍 사이에 가중치가 $x_i$인 간선이 추가됩니다.

최종적으로 얻은 그래프를 $G$라 하고, 그 연결 성분을 $G_0, G_1, \cdots, G_{k-1}$이라고 합니다. $f(G_i)$를 $G_i$의 최소 신장 트리(MST)의 크기(간선 가중치의 합)라고 할 때, $\sum_{i=0}^{k-1} f(G_i)$를 구하십시오.

정답은 $998244353$으로 나눈 나머지를 출력합니다.

입력

첫 번째 줄에는 세 개의 음이 아닌 정수 $n, a, b$가 주어집니다.

다음 $a$개의 줄에는 각각 두 개의 음이 아닌 정수 $d_i, x_i(i = 1, 2, \cdots, a)$가 주어집니다.

다음 $b$개의 줄에는 각각 세 개의 음이 아닌 정수 $u_i, v_i, w_i(i = 1, 2, \cdots, b)$가 주어집니다.

출력

정답을 $998244353$으로 나눈 나머지를 한 줄에 출력합니다.

예제

입력 1

13 2 3
4 16
5 17
10 2 3
0 7 19
5 6 12

출력 1

177

입력 2

80 5 10
35 5
68 7
4 11
67 15
21 18
1 20 13
33 48 5
37 68 16
64 72 4
22 11 13
73 17 1
24 71 9
71 30 9
16 18 2
13 2 4

출력 2

512

서브태스크

모든 테스트 케이스에 대하여: $1 \leq n \leq 10^{18}$, $0 \leq a, b \leq 5 \times 10^4$, $1 \leq d_i < n(1 \leq i \leq a)$, $0 \leq x_i < 998244353(1 \leq i \leq a)$, $0 \leq u_i, v_i < n, u_i \not= v_i(1 \leq i \leq b)$, $0 \leq w_i < 998244353(1 \leq i \leq b)$.

특수 제한 A: 모든 $x_i$와 $w_i$는 $1$입니다.

• subtask $1$($4$ pts): $n \leq 2 \times 10^5, a \leq 10$
• subtask $2$($8$ pts): $n \leq 2 \times 10^5$
• subtask $3$($6$ pts): $a = 2, b = 0$
• subtask $4$($18$ pts): $a = 2, b \leq 5 \times 10^4$
• subtask $5$($12$ pts): $a \leq 1000, b = 0$, 특수 제한 A를 만족함
• subtask $6$($12$ pts): $a \leq 1000, b \leq 200$
• subtask $7$($12$ pts): $b = 0$
• subtask $8$($10$ pts): 특수 제한 A를 만족함
• subtask $9$($18$ pts): 특수 제한 없음

참고

(참고: 출제자는 사후에 subtask $5$와 $8$의 데이터가 특이한 성질을 가지고 있음을 발견했습니다. 따라서 참가자들은 subtask $5$와 $8$을 통과하기 위해 독창적인 방법을 시도해 보는 것을 권장합니다.)