Bài tập

Trên trục số, có \(N\) đoạn thẳng. Đoạn thẳng thứ \(i\) có hai đầu nằm tại các điểm nguyên \(L_i\) và \(R_i\) \((0 \leq L_i \leq R_i \leq 10^9)\).

Bạn được phép chọn hai điểm nguyên \(x\) và \(y\) trên trục số (hai điểm này có thể trùng nhau). Một đoạn thẳng được gọi là được chọn nếu nó chứa ít nhất một trong hai điểm \(x\) hoặc \(y\).

Hãy tìm ra số đoạn được chọn lớn nhất trong tất cả các trường hợp của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \leq N \leq 10^5)\) --- số đoạn thẳng.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i\) và \(R_i\) --- biểu diễn đoạn thẳng thứ \(i\) \((0 \leq L_i \leq R_i \leq 10^9)\).

Output

• Ghi ra một số nguyên duy nhất --- số lượng đoạn thẳng được chọn nhiều nhất có thể.

Example

5
1 2
2 3
3 4
4 5
5 6

4

Scoring

• Subtask 1 (30 điểm): \(N \leq 100\), \(0 \leq L_i, R_i \leq 100\)
• Subtask 2 (20 điểm): \(N \leq 100\)
• Subtask 3 (20 điểm): \(N \leq 1000\)
• Subtask 4 (30 điểm): Không có ràng buộc bổ sung

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 

Một công ty vận tải đang cố gắng tối ưu hóa chi phí bằng cách tìm đường đi rẻ nhất để vận chuyển hàng giữa các địa điểm. Khu vực mà công ty hoạt động có hệ thống đường một chiều, mỗi con đường đều phải trả phí (gọi là toll).

Mỗi con đường nối trực tiếp 2 địa điểm \(a\) và \(b\) (với \(a < b\)), và thỏa mãn điều kiện đặc biệt: \(b \div K = a \div K + 1\)
với \(K\) là một hằng số cho trước. Ký hiệu \(\div\) là phép chia lấy nguyên (div).

Cho danh sách các con đường có phí và danh sách các đơn hàng cần vận chuyển giữa hai địa điểm, hãy giúp công ty tính chi phí thấp nhất để thực hiện từng đơn hàng. Nếu không thể đi từ \(a\) đến \(b\), hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa 4 số nguyên \(K, N, M, O\) (\(1 \le N \le 5 \cdot 10^4\), \(1 \le O \le 10^4\), \(K \le 5\))
• Mỗi dòng trong \(M\) dòng tiếp theo chứa 3 số nguyên \(a, b, t\) (\(0 \le a < b < N\), \(1 \le t \le 10^4\)) --- có đường một chiều từ \(a\) đến \(b\) với phí \(t\), thỏa mãn $
  b \div K = a \div K + 1
  $
• Mỗi dòng trong \(O\) dòng tiếp theo chứa hai số nguyên \(a, b\) (\(0 \le a < b < N\)) --- mô tả một đơn hàng cần vận chuyển từ \(a\) đến \(b\)

Output

In ra \(O\) dòng, dòng thứ \(i\) là chi phí tối thiểu để đi từ \(a\) đến \(b\) của đơn hàng thứ \(i\). Nếu không thể đi, in -1.

Scoring

• Subtask 1 (10 điểm): \(K = 1\)
• Subtask 2 (13 điểm): Tất cả đơn hàng có \(a = 0\)
• Subtask 3 (15 điểm): \(O \le 100\)
• Subtask 4 (30 điểm): \(O \le 3000\)
• Subtask 5 (32 điểm): Không giới hạn gì thêm

Example

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

15
9
7
8
-1

Nhi rất thích chơi với các dãy số nguyên, tìm kiếm số nhỏ nhất trong một dãy là một sở thích thường ngày của cô ấy.

Tuy nhiên, tìm số nhỏ nhất trong một dãy số trở nên rất dễ với cô ấy sau khi luyện tập nhiều năm, nên cô ấy quyết định tạo ra một dãy số mới \(L\) một cách độc đáo hơn như sau:

\beginlstlisting
-- lists are 1-indexed --

function generate(A, B, x):

let n = length of A
let m = length of B
let L = an empty list

for i from 1 to min(n, m - x):
    for j from (i + x) to m:
        Append (A[i]*B[j]) to the end of L

return L

\endlstlisting

Để tạo được dãy số \(L\) cuối cùng, Nhi sử dụng hai dãy số nguyên và cùng với một số nguyên và sử dụng hàm \(generate(A, B, x)\). Dãy này rất dài, tuy nhiên nó vẫn chưa đủ khó để tìm số nhỏ nhất của dãy. Vì vậy quyết định đi tìm số nhỏ thứ \(K\) của dãy mới này.

Input

--- Dòng đầu tiên chứa các số nguyên \(N, M, x, K\) \((1 \leq x < m, 1 \leq K \leq |L|)\)

--- Dòng thứ hai chứa \(N\) số nguyên mô tả dãy \(A\) \((1 \leq |A_{i}| \leq 2 \times 10^5)\)

--- Dòng thứ ba chứa \(M\) số nguyên mô tả dãy \(B\) \((1 \leq |B_{i}| \leq 2 \times 10^5)\)

Output

Ghi ra một số nguyên duy nhất là số nhỏ thứ \(K\) của dãy được tạo ra.

Example

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

3

Scoring

\(50\%\) số test có \(N, M \leq 2000\).

\(50\%\) số test có \(N, M \leq 2\times10^5\).