Bài tập

Trên một vùng không gian phẳng cực lớn được mô tả như một bảng số có kích thước \((10^9 + 1) \times (10^9 + 1)\), các hàng được đánh số từ \(0\) đến \(10^9\), các cột cũng tương tự. Ô nằm ở cột \(x\) và hàng \(y\) thì được gọi là ô \((x, y)\) với \(0 \le x, y \le 10^9\).

Ban đầu có \(N\) máy phát tín hiệu được đặt tại các ô \((x_i, y_i)\). Mỗi máy phát có hai thuộc tính:

• \(D_i\): bán kính phủ sóng của máy phát.
• \(S_i\): cường độ tín hiệu phát ra.

Máy phát tại \((x_i, y_i)\) sẽ phát sóng đến toàn bộ các ô \((x, y)\) thỏa mãn:

Nếu một ô nằm trong phạm vi phủ sóng của nhiều máy phát, cường độ tại ô đó là tổng các \(S_i\) của những máy phát phủ sóng được nó.

Có \(Q\) truy vấn, mỗi truy vấn yêu cầu bạn tính tổng cường độ tín hiệu tại một ô \((u, v)\).

\InputFile

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 2 \cdot 10^5\)) --- số lượng máy phát.
• \(N\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(x_i\), \(y_i\), \(D_i\), \(S_i\) (\(0 \le x_i, y_i \le 10^9\), \(0 \le D_i \le 10^9\), \(1 \le S_i \le 10^9\)) --- thông tin của máy phát thứ \(i\).
• Dòng tiếp theo chứa một số nguyên \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)) --- số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(u\), \(v\) --- tọa độ của ô cần truy vấn (\(0 \le u, v \le 10^9\)).

\OutputFile

In ra \(Q\) dòng, dòng thứ \(i\) là tổng cường độ tín hiệu tại ô được hỏi trong truy vấn thứ \(i\).

\Scoring

• Subtask 1 (15% số điểm): \(N \le 100\), \(0 \le x_i, y_i, u, v \le 100\), \(D_i \le 100\).
• Subtask 2 (15% số điểm): \(N \le 1000\), \(0 \le x_i, y_i, u, v \le 1000\), \(D_i \le 1000\).
• Subtask 3 (18% số điểm): \(N \le 1000\), \(Q \le 1000\).
• Subtask 4 (52% số điểm): Không có ràng buộc gì thêm.

Example

3
1 1 1 5
2 2 1 7
3 3 2 10
2
1 1
2 2

5
17

2
0 0 1 3
10 10 1 7
3
0 0
1 1
10 10

3
0
7

Với một đồ thị vô hướng liên thông, cây khung là một cách giữ lại một số ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông. Nếu các cạnh của đồ thị gốc có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh được giữ lại là nhỏ nhất.

Cho một đồ thị vô hướng liên thông có trọng số gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\), các cạnh được gán trọng số là các số nguyên dương sao cho, với mọi số nguyên dương \(c\), không tồn tại quá \(5\) cạnh có trọng số \(c\). Hãy đếm số cây khung nhỏ nhất của đồ thị này. Nói cách khác, đếm số cách giữ lại ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông và tổng trọng số các cạnh được giữ lại là nhỏ nhất.

Do kết quả có thể rất lớn, bạn chỉ cần đưa ra đáp số theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(θ\) \((1 ≤ θ ≤ 5)\) là số thứ tự cùa subtask chứa test này.

Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 3·10^5)\), lần lượt là số đỉnh và số cạnh của đồ thị.

\(m\) dòng cuối cùng, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(c\) \((1 ≤ u, v ≤ n, 1 ≤ c ≤ m)\) cho biết trên đồ thị có một cạnh nối hai đỉnh \(u\) và \(v\) với trọng số \(c\).

Dữ liệu vào đảm bảo đồ thị liên thông, và với mọi số nguyên dương \(c\), không có quá \(5\) cạnh của đồ thị có trọng số này.

Output

Gồm một số nguyên duy nhất là số cây khung nhỏ nhất của đồ thị modulo \(998244353\).

Example

1
3 3
1 2 1
2 3 1
3 1 1

3

2
4 6
1 2 1
3 4 1
1 3 2
2 4 2
1 4 3
2 3 3

2

5
4 9
1 2 1
1 2 1
2 3 2
2 3 2
2 3 2
3 4 3
3 4 3
3 4 3
3 4 3

24

Scoring

Subtask \(1\) (\(14\) điểm): \(m ≤ 7\)

Subtask \(2\) (\(18\) điểm): \(m ≤ 25\)

Subtask \(3\) (\(18\) điểm): Tồn tại tối đa một số nguyên \(c\) sao cho đồ thị có nhiều hơn một cạnh với trọng số \(c\).

Subtask \(4\) (\(20\) điểm): \(m = n\)

Subtask \(5\) (\(30\) điểm): Không có ràng buộc gì thêm.

Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), trong đó đỉnh \(1\) là gốc của cây. Tất cả các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(u\) được gọi là tổ tiên của đỉnh \(u\). Mỗi đỉnh đều có hai loại trọng số: đỉnh thứ \(i\) có trọng số của đỉnh là \(a_i\) và trọng số tổ tiên là \(b_i\).

Tổ tiên chung gần nhất của một tập đỉnh là đỉnh chung đầu tiên của các đỉnh khi đi về đỉnh gốc \(1\) (nếu tập hợp gồm \(1\) đỉnh thì tổ tiên chung gần nhất là chính đỉnh đó).

Xét một tập hợp gồm \(k\) \((0 < k \le N)\) đỉnh phân biệt bất kì \(\{u_1, u_2, \dots, u_k\}\). Gọi \(p\) là tổ tiên chung gần nhất của \(k\) đỉnh. Khi đó giá trị của tập đỉnh này được tính bằng công thức:

Vậy một cây \(N\) đỉnh sẽ có \(2^N - 1\) tập đỉnh phân biệt.

Yêu cầu. Hãy tính tổng giá trị của tất cả các tập đỉnh có thể tạo ra. Vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

\InputFile

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \le 10^6)\) là số đỉnh của cây.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((a_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số đỉnh của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
• Dòng thứ ba chứa \(N\) số nguyên dương \(b_1, b_2, \dots, b_N\) \((b_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số khi nó là tổ tiên của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) \((u, v \le N)\) mô tả một cạnh của cây.

\OutputFile

• Gồm một số nguyên duy nhất là kết quả của bài toán sau khi lấy phần dư khi chia cho \(10^9 + 7\).

\Examples
\beginexample
\exmp
3
1 1 2
2 1 2
1 2
1 3

21

\endexample

\Note
Với cây trong ví dụ (gốc \(1\), hai con là \(2\) và \(3\)):

• Tập \(\{1\}\) có giá trị: \(2\);
• Tập \(\{2\}\) có giá trị: \(1\);
• Tập \(\{3\}\) có giá trị: \(4\);
• Tập \(\{1, 2\}\) có giá trị: \(2\);
• Tập \(\{1, 3\}\) có giá trị: \(4\);
• Tập \(\{2, 3\}\) có giá trị: \(4\);
• Tập \(\{1, 2, 3\}\) có giá trị: \(4\).

Tổng là \(21\).

\Scoring

• (\(20\%\)) \(N \le 15\) và cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
• (\(20\%\)) \(N \le 15\);
• (\(20\%\)) Cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
• (\(20\%\)) Mọi trọng số đỉnh của các đỉnh đều là \(1\);
• (\(20\%\)) Không có ràng buộc thêm.

\endproblem

Cây là đồ thị vô hướng liên thông không chứa chu trình. Một cây gồm \(n\) đỉnh luôn có \(n - 1\) cạnh và giữa hai đỉnh phân biệt trên cây luôn tồn tại đường đi đơn duy nhất. Cho một cây gồm \(n\) đỉnh và mỗi cạnh của cây có một độ dài riêng. Bạn cần trả lời \(q\) câu hỏi, mỗi câu hỏi gồm hai đỉnh \(u, v\) và bạn cần cho biết khoảng cách giữa hai đỉnh \(u\) và \(v\). Nói cách khác, bạn cần tính tổng độ dài các cạnh thuộc đường đi đơn duy nhất từ \(u\) đến \(v\).

Input

Dòng đầu tiên chứa số nguyên \(θ\) \((1 ≤ θ ≤ 3)\) --- số thứ tự của subtask chứa test này.

Dòng thứ hai chứa một số nguyên \(n\) \((1 ≤ n ≤ 3·10^5)\) --- số đỉnh của cây.

\(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(c\) \((1 ≤ u, v ≤ n, 1 ≤ c ≤ 10^9)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\) với độ dài \(c\).

Dòng tiếp theo chứa một số nguyên \(q\) \((1 ≤ q ≤ 3·10^5)\) --- số câu hỏi cần trả lời.

\(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 ≤ u, v ≤ n)\) thể hiện một câu hỏi.

Output

In ra \(q\) số nguyên là khoảng cách giữa hai đỉnh \(u\) và \(v\) trên cây trong mỗi câu hỏi.

Example

1
8
1 2 2
2 6 2
1 3 7
3 4 1
3 5 9
4 7 9
1 8 7
3
5 7
6 1
3 8

19
4
14

Scoring

Subtask \(1\) (\(35\) điểm): \(n, q ≤ 300\).

Subtask \(2\) (\(25\) điểm): Cây có \(n - 1\) cạnh \((1, 2), (2, 3), ..., (n - 1, n)\).

Subtask \(3\) (\(40\) điểm): Không có ràng buộc gì thêm.