Bài tập

Vương quốc Byteland có \(N\) nút giao thông trọng điểm được đánh số từ \(1\) đến \(N\). Hệ thống đường cao tốc gồm \(M\) con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) nối nút giao thông \(X_i\) với \(Y_i\) (\(1 \le i \le M, 1 \le X_i, Y_i \le N\)) có phí đường bộ là \(Z_i\) (\(Z_i \le 10^6\)).

\begincenter

\endcenter

Ví dụ: Từ nút giao thông 1 đến nút giao thông 4 (như hình vẽ) có hai đường đi khác nhau: đường đi thứ nhất là \(1 \to 2 \to 4\) có tổng phí đường bộ là 30, đường đi thứ hai là \(1 \to 3 \to 4\) có tổng phí đường bộ là 35.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa \(K\) con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông \(S\) đến nút giao thông \(T\) sau khi được Quốc vương ban hành chính sách mới.

Input

• Dòng đầu ghi năm số nguyên dương \(N, M, K, S, T\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi ba số nguyên dương \(X_i, Y_i, Z_i\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Example

4 4 1 1 4
1 2 10
1 3 30
2 4 20
3 4 5

5 

Scoring

• Có 20% số điểm tương ứng \(1 < N, M \le 100000\) và \(K = 0\);
• Có 20% số điểm tương ứng \(1 < N \le 100, M \le 1000\) và \(K = 1\);
• Có 20% số điểm tương ứng với \(1 < N, M \le 100000\) và \(K = 1\);
• Có 40% số điểm tương ứng với \(100 < N, M \le 100000\) và \(1 < K \le 10\).

Đất nước ABC có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và các con đường nối giữa các thành phố là đường đi hai chiều. Hệ thống giao thông đó đảm bảo luôn đi được từ một thành phố bất kỳ đến một thành phố khác thông qua các đường đi.

Nam đang dự định đi du lịch đất nước ABC, chuyến đi của cậu bắt đầu từ thành phố \(s\) và kết thúc tại thành phố \(t\). Nam có thể di chuyển tự do giữa các thành phố và cậu có thể thăm lại thành phố mà cậu đã thăm với số lần tùy thích, nhưng nếu đến thành phố \(t\) thì Nam sẽ kết thúc hành trình của mình. Nam sẽ chụp một bức ảnh ở thành phố đầu tiên của chuyến đi nếu \(s \le t\). Sau đó, mỗi khi cậu đến một thành phố có chỉ số lớn hơn tất cả thành phố đã được thăm, cậu sẽ chụp thêm một bức ảnh ở thành phố đó. Đồng thời, Nam cũng muốn chụp một bức ảnh ở thành phố kết thúc nếu nó thỏa mãn điều kiện chụp ảnh trên.

Yêu cầu: Nam có \(q\) lựa chọn, mỗi lựa chọn cho biết thành phố xuất phát \(s\) và thành phố kết thúc \(t\). Bạn hãy cho biết số lượng ảnh tối đa cậu ấy có thể chụp trong suốt chuyến đi từ \(s\) đến \(t\), hoặc không có hành trình nào với điều kiện như vậy.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(1 \le n \le 5000\), \(n-1 \le m \le \min(\frac{n(n-1)}{2}, 5000)\)) lần lượt là số thành phố ở đất nước ABC và số con đường nối các thành phố.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) (\(1 \le u, v \le n\)) thể hiện một đường đi hai chiều nối hai thành phố \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 2 \times 10^5\)) là số lựa chọn của Nam.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(s, t\) (\(1 \le s, t \le n\)) thể hiện một lựa chọn của Nam.

Các số trên một dòng ghi cách nhau bởi dấu cách.

Output

• Gồm \(q\) dòng, theo thứ tự lựa chọn của Nam trong tệp dữ liệu vào, mỗi dòng ghi một số là số lượng bức ảnh lớn nhất mà Nam chụp được trong hành trình lựa chọn đó. Nếu không có hành trình như vậy thì ghi ra \(-1\).

Example

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

2
2
-1
1

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

4
-1

3 2
1 3
3 2
2
1 1
1 2

1
-1

Scoring

• 20% số tests tương ứng với 20% số điểm của bài có: \(q \le 1000, s+1 = t\) với mọi lựa chọn.
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000, q \le 1000\).
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000\).
• 40% số tests còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Có một bãi đỗ xe hình vòng tròn gồm \(n\) chỗ trống, được đánh số từ \(1\) đến \(n\).
Có \(n\) chiếc xe lần lượt đi vào bãi để đỗ.

Chiếc xe thứ \(i\) muốn đỗ ở vị trí \(p_i\).
Nếu vị trí đó đã bị chiếm, xe sẽ tiếp tục di chuyển theo chiều tăng của chỉ số (theo vòng tròn) cho đến khi gặp chỗ trống đầu tiên, rồi dừng lại ở đó.

Yêu cầu: Xác định vị trí mà mỗi xe sẽ đỗ.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 5 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \ldots, p_n\) \((1 \le p_i \le n)\).

\OutputFile

• In ra \(n\) số nguyên. Số thứ \(i\) là vị trí bãi đỗ của chiếc xe thứ \(i\).

\Scoring

• Có \(40\%\) số điểm ứng với \(n \le 1000\).

Example

3
2 2 2

2 3 1 

Tại vùng ngoại ô rừng sâu, lễ hội ánh sáng ở thị trấn Aurora đang diễn ra --- một sự kiện chỉ xảy ra mỗi 10 năm một lần. Hana, một cô gái trẻ đầy tò mò, quyết định đi bộ xuyên rừng từ ngôi làng nơi cô sống (tọa độ \(x = 0\)) đến Aurora, cách đó \(X\) mét.

Cô bắt đầu hành trình với năng lượng ban đầu là \(D\). Để tiếp tục di chuyển, cô cần tiêu tốn đúng 1 đơn vị năng lượng cho mỗi mét đi bộ. Nếu năng lượng của cô giảm xuống dưới \(0\) tại bất kỳ thời điểm nào, Hana sẽ kiệt sức và không thể tiếp tục hành trình.

May mắn thay, dọc đường có \(n\) trạm tiếp sức, mỗi trạm cung cấp cho cô một ít thực phẩm hoặc nước giúp hồi phục năng lượng. Trạm thứ \(i\) nằm tại vị trí \(x_i\) trên tuyến đường và nếu dừng lại tại đó, Hana sẽ nhận thêm \(y_i\) đơn vị năng lượng. Mỗi trạm chỉ có thể sử dụng đúng một lần.

Hana muốn biết: tối thiểu cô cần dừng lại ở bao nhiêu trạm tiếp sức để có thể chắc chắn đến được Aurora mà không bao giờ cạn kiệt năng lượng.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(D\), \(X\) \((1 \leq n \leq 2 \cdot 10^5,\ 1 \leq D, X \leq 10^9)\) --- số lượng trạm tiếp sức, năng lượng ban đầu, và khoảng cách từ làng đến Aurora.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) \((1 \leq x_i < X)\) --- vị trí của các trạm tiếp sức.
• Dòng thứ ba chứa \(n\) số nguyên \(y_1, y_2, \dots, y_n\) \((1 \leq y_i \leq 10^9)\) --- năng lượng nhận được tại mỗi trạm tương ứng.

Output

• In ra một số nguyên duy nhất --- số trạm tiếp sức tối thiểu mà Hana cần dừng lại để đến được Aurora. Nếu không có cách nào để đến nơi, in ra -1.

Example

5 5 12
3 4 7 8 11
3 2 1 2 1

3

5 10 40
1 20 30 2 38
7 7 7 7 7

5

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 30 & \(y_i = y_j\) với mọi \(i, j\)

2 & 30 & \(n \leq 1000\)

3 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular