Cho một đồ thị vô hướng có trọng số với $n$ đỉnh, các đỉnh được đánh số từ $\{0, 1, \cdots, n - 1\}$. Ban đầu đồ thị có $b$ cạnh, cạnh thứ $i$ nối giữa $u_i$ và $v_i$ với trọng số $w_i$.

Tiếp theo, thực hiện $a$ thao tác liên tiếp. Trong thao tác thứ $i$, một cạnh có trọng số $x_i$ được thêm vào giữa mọi cặp đỉnh có khoảng cách chỉ số là $d_i$.

Gọi đồ thị cuối cùng thu được là $G$, với các thành phần liên thông là $G_0, G_1, \cdots, G_{k-1}$. Gọi $f(G_i)$ là trọng số của cây khung nhỏ nhất của $G_i$ (tổng trọng số các cạnh). Hãy tính $\sum_{i=0}^{k-1} f(G_i)$.

Kết quả cần được lấy dư theo $998244353$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên không âm $n, a, b$.

$a$ dòng tiếp theo, mỗi dòng chứa hai số nguyên không âm $d_i, x_i (i = 1, 2, \cdots, a)$.

$b$ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm $u_i, v_i, w_i (i = 1, 2, \cdots, b)$.

Dữ liệu ra

Một dòng duy nhất chứa một số nguyên không âm là kết quả sau khi lấy dư theo $998244353$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

177

Dữ liệu vào 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

Dữ liệu ra 2

512

Xem các tệp đính kèm cho ví dụ 3 và 4.

Nhiệm vụ con

Với mọi bộ dữ liệu: $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 \neq v_i (1 \leq i \leq b)$, $0 \leq w_i < 998244353 (1 \leq i \leq b)$.

Giới hạn đặc biệt A: Tất cả $x_i$ và $w_i$ đều bằng $1$.

• Subtask 1 (4 điểm): $n \leq 2 \times 10^5, a \leq 10$.
• Subtask 2 (8 điểm): $n \leq 2 \times 10^5$.
• Subtask 3 (6 điểm): $a = 2, b = 0$.
• Subtask 4 (18 điểm): $a = 2, b \leq 5 \times 10^4$.
• Subtask 5 (12 điểm): $a \leq 1000, b = 0$, thỏa mãn giới hạn đặc biệt A.
• Subtask 6 (12 điểm): $a \leq 1000, b \leq 200$.
• Subtask 7 (12 điểm): $b = 0$.
• Subtask 8 (10 điểm): Thỏa mãn giới hạn đặc biệt A.
• Subtask 9 (18 điểm): Không có giới hạn đặc biệt.

(Lưu ý: Người ra đề phát hiện sau đó rằng dữ liệu của subtask 5 và 8 có các tính chất đặc biệt kỳ lạ, vì vậy khuyến khích thí sinh tự thử nghiệm các phương pháp tiếp cận khác nhau để giải quyết subtask 5 và 8.)