Bài tập

Nhà khoa học Alex đang thực hiện một cuộc thám hiểm để nghiên cứu các mẫu vật tại \(n\) địa điểm khác nhau. Anh ấy bắt đầu chuyến đi từ địa điểm \(1\). Giữa một số địa điểm có các con đường bộ hai chiều, và Alex biết thời gian cần thiết để đi qua mỗi con đường.

Ngoài ra, giữa mỗi cặp địa điểm còn có một tuyến đường hàng không, nhưng do một sự cố kỹ thuật gần đây, thời gian di chuyển giữa hai địa điểm \(u\) và \(v\) bằng đường hàng không được tính bằng \((u - v)^2\).

Vì Alex không thích bay cho lắm, anh ta chỉ có thể sử dụng tối đa \(k\) chuyến bay trong suốt hành trình của mình. Mục tiêu của Alex là tìm thời gian di chuyển tối thiểu từ địa điểm \(1\) đến mỗi địa điểm khác.

Yêu cầu: Hãy giúp Alex tính toán thời gian di chuyển tối thiểu từ địa điểm \(1\) đến mỗi địa điểm trong số \(n\) địa điểm.

Input

• Dòng đầu tiên của input chứa ba số nguyên \(n, m, k\) (\(2 \le n \le 10^5, 1 \le m \le 10^5, 0 \le k \le 20\)) lần lượt là số địa điểm, số con đường bộ và số chuyến bay tối đa mà Alex có thể sử dụng.
• \(m\) dòng tiếp theo mô tả các con đường bộ. Mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le n, u \ne v, 1 \le w \le 10^9\)) --- hai địa điểm được kết nối và thời gian di chuyển qua con đường đó. Lưu ý rằng một số cặp địa điểm có thể được kết nối bởi nhiều hơn một con đường.

Output

• In ra \(n\) số nguyên, số thứ \(i\) là thời gian di chuyển tối thiểu đến địa điểm \(i\).

Example

3 1 2
1 3 1

0 1 1 

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

0 1 4 6 

Scoring

• Subtask \(1\) (25% số điểm) : \(k = 0\).
• Subtask \(2\) (25% số điểm) : \(n, m \leq 50\).
• Subtask \(3\) (25% số điểm) : Đồ thị có dạng đường thẳng.
• Subtask \(4\) (25% số điểm) : Không có ràng buộc gì thêm.

Trong giờ học Vật lý, một thành viên của CLB CHTCoder đang lơ đãng nhớ về crush thì bị thầy phát hiện.

Để không bị trừ điểm hoặc ghi vào sổ đầu bài, thầy đã giao cho hai bạn một thử thách:
Cho một bảng kích thước \(n \times n\), trong đó các số được điền theo thứ tự tăng dần từ trái sang phải và từ trên xuống dưới, bắt đầu từ \(1\) cho tới \(n \times n\).

Yêu cầu của thầy rất đơn giản: Tính tổng các phần tử nằm trên đường chéo chính của bảng.

Input

Đọc từ file NHOEM.INP:

• Số nguyên dương \(t\) (\(1 \le t \le 10^{6}\)) --- số câu hỏi.
• Mỗi dòng tiếp theo chứa một số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

Ghi ra file NHOEM.OUT:

• Gồm \(t\) dòng, mỗi dòng là tổng đường chéo chính tương ứng.

Example

2
3
6

15
111

Scoring

• Subtask 1 (70%): \(1 \le t, n \le 10^{3}\).
• Subtask 2 (30%): Không có ràng buộc thêm.

Cho mảng \(A\) gồm \(n\) phần tử. Một dãy con của \(A\) là một dãy thu được bằng cách chọn một số phần tử theo thứ tự tăng dần chỉ số (không nhất thiết liên tiếp).
Yêu cầu: đếm số dãy con khác nhau và khác rỗng của \(A\).

\InputFile

• Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\) (\(1 \le A_i \le 10^6\)).

\OutputFile
In ra số lượng dãy con khác nhau, modulo \(123456789\).

Example

3
1 2 1

6

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