Bài tập

Sau chuỗi ngày ôn và thi mệt mỏi, Bờm quyết định du lịch đến đất nước Byteland. Đất nước xinh đẹp này có \(n\) thành phố, các thành phố kết nối với nhau bởi \(n-1\) con đường hai chiều. Con đường thứ \(i\) nối từ thành phố \(x\) đến thành phố \(y\) có độ dài \(w\).

Thêm nữa, qua quá trình khảo sát Bờm có lên thang điểm về độ đẹp cho mỗi thành phố. Độ đẹp của thành phố thứ \(i\) được đánh giá là \(a_i\).

Việc đi lại giữa các thành phố được thực hiện bằng xe buýt. Cách vận hành xe buýt ở đây cũng rất đặc biệt:

Giả sử xe buýt đang ở thành phố \(u\), nó sẽ xác định tuyến đi tiếp theo bằng cách chọn một thành phố \(v\) (\(v \neq u\) và có thể \((u,v)\) không có cạnh nối) sao cho giá trị \(a_v - d(u, v)\) là lớn nhất. Trong đó \(d(u, v)\) được định nghĩa là khoảng cách đi từ \(u\) đến \(v\). Nếu có nhiều thành phố thỏa mãn thì xe buýt sẽ di chuyển đến thành phố có chỉ số nhỏ nhất. Khi đã chọn được điểm đến là thành phố \(v\), xe buýt sẽ đi thẳng từ \(u\) đến \(v\) mà không dừng ở các thành phố trung gian.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có hai tham số \(s, k\) ứng với việc Bờm xuất phát từ thành phố \(s\) và di chuyển qua \(k\) tuyến đường bằng xe buýt theo cách mô tả ở trên. Hãy cho biết, với mỗi truy vấn thì Bờm sẽ kết thúc chuyến đi ở thành phố nào?

Input

• Dòng đầu chứa hai số nguyên dương \(n, Q\) (\(n, Q \leq 2 \times 10^5\)) là số thành phố và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) là độ đẹp của các thành phố (\(|a_i| \leq 10^9\)).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x, y, w\) mô tả một con đường hai chiều (\(1 \leq x, y \leq n,~ 0 < w \leq 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s, k\) mô tả một truy vấn: thành phố xuất phát \(s\) và số tuyến đường \(k\) (\(1 \le s \le n\), \(k \le 10^6\)).

Output

Gồm \(Q\) dòng, mỗi dòng in ra chỉ số thành phố mà Bờm sẽ kết thúc chuyến đi ở mỗi truy vấn.

Example

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

5
3
3
1

Scoring

• Có 20% số test với \(n, Q \leq 200,~ k \leq 200\).
• Có 25% số test khác với \(n, Q \leq 2000\).
• Có 25% số test khác với \(k = 1\).
• Số test còn lại không có ràng buộc gì thêm.

Cho một quân mã được đặt trên mặt phẳng tọa độ Descartes. Trong mỗi bước di chuyển, quân mã có thể đi theo một trong bốn vector chỉ phương \((2, -1)\); \((2, 1)\); \((1, 2)\) và \((-1, 2)\) như hình vẽ dưới đây:

\begincenter

\endcenter

Cho biết quân mã đang ở điểm có tọa độ \((x_1, y_1)\) và quân mã cần đi tới điểm có tọa độ \((x_2, y_2)\). Hãy đếm số cách quân mã có thể làm được điều này. Do kết quả có thể rất lớn, hãy in ra theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 10^5)\) là số câu hỏi.

\(t\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) \((1 \leq x_1, y_1, x_2, y_2 \leq 2000)\) cho biết vị trí xuất phát và vị trí cần tới của quân mã.

Output

In ra \(t\) số nguyên là đáp án của \(t\) câu hỏi \(–\) số cách để quân mã đi từ vị trí xuất phát tới vị trí kết thúc, theo modulo \(998244353\).

Example

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

3
1
0

Scoring

• Subtask \(1\) (\(20\) điểm): \(x_1, y_1, x_2, y_2 \leq 5\)

• Subtask \(2\) (\(15\) điểm): \(x_1, y_1, x_2, y_2 \leq 100\) và \(t \leq 10\)

• Subtask \(3\) (\(15\) điểm): \(x_1, y_1, x_2, y_2 \leq 100\)

• Subtask \(4\) (\(25\) điểm): \(x_1, y_1, x_2, y_2 \leq 2000\) và \(t \leq 10\)

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

Vương quốc Lakasi là một vương quốc mới thành lập, nhà vua muốn mở rộng phạm vi lãnh thổ nên quyết định đi khai phá các vùng đất mới. Nhà vua quyết định mỗi một vùng đất sau khi khai thác thì xây dựng một thành phố ở đó cùng với đó là các con đường nối giữa các thành phố với nhau sao cho khi hoàn thành công việc mở rộng lãnh thổ thì tất cả các thành phố và các con đường tạo thành một đồ thị dạng cây. Hiện ban đầu nhà vua đang ở thủ đô và xem đó như là đỉnh \(1\). Các thành phố còn lại xem như là các đỉnh con trong cây có gốc là đỉnh \(1\). Trong quá trình xây dựng, có \(Q\) sự kiện diễn ra gồm 2 loại:

• Add x y -- thêm một đỉnh mới là một đỉnh con có đường đi độ dài \(y\) nối với đỉnh \(x\). Đỉnh mới được thêm sẽ có chỉ số bằng số lượng đỉnh trong đồ thị hiện tại.

• Query a b -- Nhà vua muốn biết độ dài đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\) là bao nhiêu. Độ dài của một đường đi được tính bằng tổng xor (exclusive or) của tất cả các con đường thuộc đường đi đó.

Đối với sự kiện loại 2, hãy trả lời câu hỏi của nhà vua.

Input

• Dòng đầu tiên chứa một số nguyên dương \(Q\) \((Q\leq 200000)\).

• \(Q\) dòng tiếp theo, mỗi dòng có dạng 1 trong 2 sự kiện trên. Các giá trị \(x,a,b\) không vượt quá số lượng đỉnh hiện tại, giá trị \(y\) không quá \(2^{30}\).

Output

• Với sự kiện loại 2, hãy in ra đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\).

Example

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

5
7

Scoring

• Subtask 1 (\(10\%\) số điểm): \(Q\leq 200\).

• Subtask 2 (\(25\%\) số điểm): \(Q\leq 2000\).

• Subtask 3 (\(25\%\) số điểm): Tất cả sự kiện loại 2 đều có \(b=1\).

• Subtask 4 (\(40\%\) số điểm): Không có giới hạn gì thêm.

Trong buổi lễ mừng chiến thắng tại học viện Chiến lược và Sáng tạo, các thí sinh được tham gia vào một trò chơi mang tên chia kho báu. Có \(N\) kho báu được đặt rải rác trên mặt phẳng tọa độ. Kho báu thứ \(i\) nằm tại ô có tọa độ \((x_i, y_i)\) và có giá trị \(w_i\).

BTC cho phép 4 người chơi chia kho báu theo cách đặc biệt: họ được chọn một cặp số \((X, Y)\) với \(1 \le i < N\). Sau đó, mỗi người sẽ nhận các kho báu nằm trong vùng tương ứng:

• Người thứ nhất nhận các kho báu tại ô có \(x_i < X\) và \(y_i < Y\)
• Người thứ hai nhận các kho báu tại ô có \(x_i < X\) và \(y_i > Y\)
• Người thứ ba nhận các kho báu tại ô có \(x_i > X\) và \(y_i < Y\)
• Người thứ tư nhận các kho báu tại ô có \(x_i > X\) và \(y_i > Y\)

Giá trị của mỗi người là tổng các \(w_i\) của những kho báu họ nhận được. Với mỗi cặp \((X, Y)\), họ sẽ tính chênh lệch lớn nhất giữa hai người bất kỳ. Trong trường hợp lý tưởng là họ nhận được cùng một giá trị thưởng, nhưng thực tế luôn phũ phàng và nếu đã không thể đồng đều, thì 4 người trên muốn chọn (X,Y) sao cho chênh lệch lớn nhất là nhỏ nhất có thể.

Yêu cầu: Với mỗi \(X = i + 0.5\) \((1 \le i < N)\), hãy tìm giá trị chênh lệch nhỏ nhất có thể giữa người nhận được nhiều kho báu nhất và người nhận được ít nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) --- số kho báu \((1 \le N \le 2 \cdot 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x_i\), \(y_i\), \(w_i\) --- tọa độ và giá trị của kho báu thứ \(i\) \((1 \le x_i, y_i \le n, 1 \le w_i \le 10^9)\).

Output

• In ra \(N - 1\) dòng, dòng thứ \(i\) chứa số nguyên duy nhất là chênh lệch nhỏ nhất có thể giữa hai người, khi \(X = i + 0.5\).

Example

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

9
8
2
6

Scoring

• Subtask 1 (11 điểm): \(1 \le N \le 200\)
• Subtask 2 (14 điểm): \(1 \le N \le 5000\)
• Subtask 3 (48 điểm): \(1 \le N \le 10^5\)
• Subtask 4 (27 điểm): Không có ràng buộc bổ sung