Bài tập

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.

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.

Bạn có bao giờ để ý rằng khi ở trong một thang máy chật hẹp, những người ở trong (phía xa hơn so với cửa) nếu muốn dừng tại một tầng, thì khi đó họ phải nhờ những người ở ngoài tránh qua hoặc đi ra khỏi thang máy thì họ mới dừng tại tầng đó được.

Hôm nay bạn gặp một tình huống tương tự, bây giờ bạn đang ở trong một thang máy rất dài đủ cho bất kì số người nào, nhưng lại quá hẹp để hai người có thể đứng cạnh nhau. Thay vào đó, thì những người trong thang máy lại phải xếp một hàng dọc.

Hiện trong thang máy có \(N\) người, theo thứ tự từ gần đến xa cửa thang máy, người thứ \(i\) muốn dừng tại tầng \(a_i\). Khi thang máy dừng ở một tầng, người cần ra ở tầng đó sẽ bước ra, nhưng nếu có người đứng trước họ thì những người đó phải tạm thời bước ra trước rồi mới quay lại. Khi quay lại, họ có thể tự do xếp lại vị trí của mình. Lưu ý chỉ những người đã bước ra trong lượt đó mới có thể sắp xếp vị trí với nhau.

Bạn quan sát tình huống này và tự hỏi: tổng cộng sẽ có bao nhiêu lượt người bước ra khỏi thang máy nếu mọi người luôn trở lại vị trí tối ưu?

Không dừng lại ở đó, bạn còn tò mò nhiều hơn và tự đặt ra \(q\) câu hỏi. Câu hỏi thứ \(i\) là nếu ban đầu không có những người ở vị trí \(x_1, x_2, \cdots x_i\) đứng trong thang máy, thì số lượt ra vào nhỏ nhất là bao nhiêu?

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((0 \leq q \lt n \leq 5 \cdot 10^5)\) --- số người ban đầu và số câu hỏi.

Dòng thứ hai chứa \(n\) số nguyên phân biệt \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq n)\) --- tầng mà người thứ \(i\) muốn đến.

Mỗi dòng trong \(q\) dòng tiếp theo chứa một số nguyên \(x_i\) \((1 \leq x_i \leq n)\). Đảm bảo \(x_i\) phân biệt.

Output

In ra \(q+1\) số trên một dòng:

• Số đầu tiên là số lượt bước ra khỏi thang máy trong trạng thái ban đầu.
• \(q\) số tiếp theo là số lượt nếu giả sử không có những người ở vị trí \(x_1, x_2, \cdots x_i\) đứng trong thang máy.

Example

5 2
3 4 1 2 5
3 2

9 6 4 

7 0
4 5 2 1 6 3 7

13 

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Giới hạn

\hline
1 & 16 & \(n, q \leq 100\)

2 & 19 & \(n, q \leq 1\,000\)

3 & 25 & \(q = 0\)

4 & 40 & Không có ràng buộc khác

\hline
\endtabular

Bạn được cung cấp một đồ thị vô hướng, có trọng số và liên thông, bao gồm \(n\) đỉnh và \(m\) cạnh. Đảm bảo rằng đồ thị không có khuyên (self-loops) và các cạnh lặp.

Định nghĩa trọng số của một đường đi:

Giả sử đường đi có \(k\) cạnh với các chỉ số \(e_1, e_2, \ldots, e_k\). Trọng số của đường đi được xác định bởi công thức:

\(\text{weight of path} = \sum_{i=1}^k w_{e_i} - \max_{i=1}^k w_{e_i} + \min_{i=1}^k w_{e_i}\)

Nhiệm vụ:

Với mỗi đỉnh \(i\) (\(2 \le i \le n\)), hãy tìm trọng số nhỏ nhất của đường đi từ đỉnh \(1\) đến đỉnh \(i\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq 2 \cdot 10^5)\) --- số đỉnh và số cạnh của đồ thị.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(v_i, u_i, w_i\) \((1 \leq v_i, u_i \leq n; 1 \leq w_i \leq 10^9; v_i \neq u_i)\) --- các đỉnh của cạnh thứ \(i\) và trọng số tương ứng.

Output

• In \(n-1\) số nguyên trên một dòng, mỗi số tương ứng với trọng số nhỏ nhất của đường đi từ đỉnh \(1\) đến đỉnh \(i\) \((2 \leq i \leq n)\).

Example

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

1 2 2 4 

6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4

2 1 4 3 1 

7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4

3 4 2 7 7 3 

Scoring

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 10\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 100\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 500\), \(w_{i}= a\) hoặc \(w_{i} = b\) với \(a\), \(b\) là hằng số.

• \(25\%\) số test tương ứng với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.