Bài tập

Đất nước Z có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và được nối với nhau bởi \(n - 1\) con đường để đảm bảo đi lại giữa hai thành phố bất kỳ. Mức độ phát triển của thành phố \(i\ (1 \le i \le n)\) là \(p_i\). Chính phủ thực hiện một dãy gồm \(q\) các công việc thuộc một trong hai loại sau:

• Loại \(1\) có dạng \(1\ i\ x\), nghĩa là đầu tư vào thành phố \(i\ (1 \le i \le n)\) để tăng mức độ phát triển của thành phố \(i\) thêm \(2x\), mức độ phát triển của các thành phố liền kề \(i\) cũng được tăng thêm \(x\).

• Loại \(2\) có dạng \(2\ i\), nghĩa là tính độ hưng thịnh của cụm các thành phố khi lấy \(i\) làm trung tâm, giá trị này được tính bằng mức độ phát triển của thành phố \(i\) và tất cả các thành phố kề \(i\).

Yêu cầu: Với mỗi công việc loại \(2\) đưa ra giá trị cần tính.

Input

• Dòng đầu chứa hai số nguyên \(n, q\ (n \le 3 \times 10^5; q \le 3 \times n)\).
• Dòng tiếp theo là \(n\) số nguyên không âm \(p_1, p_2, \ldots, p_n\ (p_i \le 10^9)\).
• Tiếp theo là \(n - 1\) dòng, mỗi dòng là một cặp số nguyên \(u, v\) mô tả có con đường nối thành phố \(u\) với thành phố \(v\).
• Tiếp theo là \(q\) dòng, mỗi dòng mô tả công việc mà chính phủ thực hiện.

Output

• Với mỗi công việc loại \(2\), đưa ra giá trị cần tính.

Example

3 5
0 0 0
1 2
2 3
1 1 1
1 2 2
2 1
2 2
2 3

9
11
7

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.

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.