Bài tập

Cho một dãy số nguyên không âm \(a_1,a_2,\ldots,a_n\) và một số nguyên \(\delta\).

• Đếm số dãy con liên tiếp, khác rỗng mà với mọi hai phần tử bất kỳ trong dãy con đó, chênh lệch không vượt quá \(\delta\) (tức \(\max-\min \le \delta\)).
• Đếm số dãy con, khác rỗng mà với mọi hai phần tử bất kỳ trong dãy con đó, chênh lệch không vượt quá \(\delta\).

Kết quả có thể rất lớn, hãy in ra hai đáp án theo modulo \(998244353\).

\InputFile

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(\delta\) (\(1 \le n \le 5\cdot 10^5\), \(0 \le \delta \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,\ldots,a_n\) (\(0 \le a_i \le 10^9\)).

\OutputFile

In ra hai số nguyên không âm trên một dòng, lần lượt là đáp án của (1) và (2), đều modulo \(998244353\).

\Scoring
\begin itemize

• Có \(35\%\) số điểm ứng với \(n \le 20\).
• Có \(25\%\) số điểm ứng với \(a_1 \le a_2 \le \cdots \le a_n\).
• \(40\%\) số điểm không có ràng buộc gì thêm.
  \end itemize

Example

3 1
1 3 2

4 5

5 4
1 2 3 4 5

15 31

6 0
0 0 1 1 1 0

10 14

Khi nghiên cứu về lý thuyết đồ thị, Thuận đưa ra một đặc trưng cho cây.

Cho một cây gồm \(n\) đỉnh, đỉnh \(i\) \((1 \le i \le n)\) có trọng số \(w_i\).
Với hai đỉnh \(i, j\), gọi \(f(i,j)\) là độ mất cân bằng giữa \(i\) và \(j\), được định nghĩa như sau:

Xét đường đi đơn trên cây từ \(i\) đến \(j\) (bao gồm cả \(i\) và \(j\)).
Gọi \(W_{\max}\) là trọng số lớn nhất và \(W_{\min}\) là trọng số nhỏ nhất trong các đỉnh nằm trên đường đi đó.
Khi đó
$
f(i,j) = W_{\max} - W_{\min}.
$

Độ mất cân bằng \(T\) của cây được định nghĩa là tổng độ mất cân bằng của mọi cặp đỉnh:

Yêu cầu. Cho một cây và trọng số các đỉnh, hãy tính giá trị \(T\).

\InputFile

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(w_1, w_2, \dots, w_n\) \((1 \le w_i \le 10^6)\).
• \(n-1\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(u_k, v_k\) \((1 \le u_k, v_k \le n)\) mô tả một cạnh của cây.

\OutputFile

• In ra một số nguyên là giá trị \(T\).

\Scoring

• (20%) Subtask 1: \(n \le 700\);
• (20%) Subtask 2: \(n \le 7000\);
• (20%) Subtask 3: \(1 \le w_i \le 2\);
• (20%) Subtask 4: \(n \le 10^5\);
• (20%) Subtask 5: \(n \le 10^6\).

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

8

\exmp
4
1 2 2 2
1 2
2 3
3 4

3

\endexample

\Note
Với mỗi cặp có thứ tự \((i,j)\), ta xét đường đi từ \(i\) đến \(j\), lấy trọng số lớn nhất và nhỏ nhất trên đường đi đó để tính \(f(i,j)\), sau đó cộng cho mọi \(i, j\) từ \(1\) đến \(n\).
Lưu ý rằng \(f(i,i)=0\), và tổng \(T\) tính trên các cặp có thứ tự.

\endproblem

Thành phố Ngân là một trong những trung tâm đô thị phát triển bậc nhất, với mạng lưới giao thông hiện đại nhưng phức tạp. Hệ thống bao gồm \(n\) nút giao thông (tượng trưng cho các ngã tư, vòng xuyến, hay điểm giao giữa các tuyến đường) và \(m\) tuyến đường một chiều nối các nút này.

Tuy nhiên, dưới áp lực dân số tăng cao và sự phát triển kinh tế, chính quyền thành phố buộc phải đánh giá lại hệ thống hạ tầng và tìm giải pháp tối ưu hoá thời gian di chuyển trong nội đô. Việc này đòi hỏi các chuyên gia thuật toán, như bạn, tìm ra những cải tiến hiệu quả nhất với chi phí thấp nhất.

Mỗi tuyến đường trong thành phố là một đoạn một chiều cho phép đi từ nút $u_i$ đến nút $v_i$, và mất $t_i$ đơn vị thời gian để đi qua. Thành phố muốn tìm cách rút ngắn thời gian đi từ trung tâm hành chính (nút $1$) đến các khu vực khác (nút $s$) bằng cách **nâng cấp một tuyến đường bất kỳ**. Sau khi được nâng cấp, thời gian qua tuyến đó giảm còn đúng $t_0$.

**Lưu ý:** Chỉ được phép nâng cấp nhiều nhất một tuyến đường. Bạn không thể nâng cấp nhiều tuyến đường cùng lúc.

Input

• Dòng đầu gồm ba số nguyên \(n\), \(m\), \(q\) --- số nút, số tuyến đường, và số yêu cầu truy vấn \((1 \le n \le 2000,\ 1 \le m \le 10^4,\ 1 \le q \le 2 \cdot 10^6)\).
• \(m\) dòng tiếp theo: mỗi dòng gồm ba số nguyên \(u_i\), \(v_i\), \(t_i\) --- mô tả tuyến đường đi từ \(u_i\) đến \(v_i\) với thời gian gốc là \(t_i\) \((1 \le u_i, v_i \le n; u_i \ne v_i; 1 \le t_i \le 2000)\).
• \(q\) dòng tiếp theo: mỗi dòng gồm hai số nguyên \(s\) và \(t_0\) --- tương ứng là điểm đến và thời gian sau khi nâng cấp \((1 \le s \le n; 1 \le t_0 \le 2000)\).

Output

Ghi ra \(q\) dòng, dòng thứ \(j\) là thời gian ngắn nhất để đi từ nút \(1\) đến nút \(s\) của truy vấn thứ \(j\), khi được phép nâng cấp nhiều nhất một tuyến đường.

Nếu không thể đi từ nút $1$ đến nút $s$ (dù nâng cấp bất kỳ tuyến nào), in ra `-1`.

Example

4 4 3
1 2 6
2 4 10
1 3 16
3 4 4
3 14
4 14
4 11

14
16
15

Scoring

• Subtask 1 (30% số điểm): \(n \le 20\), \(q \le 200\).
• Subtask 2 (40% số điểm): \(n \le 200\), \(q \le 2000\).
• Subtask 3 (30% số điểm): \(n \le 2000\), \(q \le 2 \cdot 10^6\).

Cho một đồ thị vô hướng là cây gồm \(N\) đỉnh. Xét hai tập đỉnh \(A\) và \(B\), ban đầu tập \(A\) chứa toàn bộ \(N\) đỉnh trên cây, còn tập \(B\) rỗng.

Gọi khoảng cách giữa hai đỉnh \(u, v\) là số cạnh ít nhất cần đi qua để đi từ \(u\) đến \(v\) trên cây. Đường kính của một tập đỉnh được định nghĩa là khoảng cách xa nhất giữa hai đỉnh bất kỳ trong tập đó.

Bạn được yêu cầu xử lý \(Q\) truy vấn. Truy vấn thứ \(i\) là một số nguyên \(v_i\), tương ứng với việc xoá đỉnh \(v_i\) khỏi tập \(A\) và thêm nó vào tập \(B\).

Sau mỗi truy vấn, hãy in ra đường kính của tập \(A\) và tập \(B\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \le N \le 4 \cdot 10^5, 1 \le Q < N)\) --- số đỉnh của cây và số truy vấn.
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a, b\) \((1 \le a, b \le N)\) mô tả một cạnh nối giữa hai đỉnh \(a\) và \(b\).
• Dòng tiếp theo gồm \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên \(v_i\) \((1 \le v_i \le N)\) --- truy vấn thứ \(i\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) in ra hai số nguyên --- đường kính của tập \(A\) và đường kính của tập \(B\) sau truy vấn thứ \(i\).

Example

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

4 0
4 1
1 2
0 3

Scoring

• Subtask 1 (20 điểm): \(N, Q \le 500\)
• Subtask 2 (20 điểm): \(N \le 2 \cdot 10^4\), \(Q \le 10^3\)
• Subtask 3 (20 điểm): Mỗi đỉnh có tối đa hai cạnh nối với nó.
• Subtask 4 (20 điểm): Khoảng cách giữa hai đỉnh xa nhất trong cây không vượt quá 40.
• Subtask 5 (20 điểm): Không có ràng buộc gì thêm.