Cho hai mảng A (kích thước N) và B (kích thước M). Hãy đếm số cặp (i, j) sao cho A[i] + B[j] <= K.

Dữ liệu vào:

Dòng 1: Ba số nguyên N, M, K (1 <= N, M <= 10^5, |K| <= 10^9).

Dòng 2: N số nguyên A[i].

Dòng 3: M số nguyên B[j].

Dữ liệu ra:

Số lượng cặp thỏa mãn.

Ví dụ:

Input:

3 3 10 
1 5 8 
2 4 9

Output:

6

Tại một phòng khám tư nhân, có N bệnh nhân đang chờ đến lượt vào khám. Bệnh nhân thứ i đến phòng khám tại thời điểm T[i] và bác sĩ cần đúng D[i] thời gian để khám xong cho người này. Vì phòng khám chỉ có một bác sĩ, nên nếu bác sĩ đang bận khám cho người trước đó, bệnh nhân đến sau sẽ phải ngồi xếp hàng chờ. Các bạn hãy xác định thời điểm mà bác sĩ hoàn thành việc khám bệnh cho tất cả N bệnh nhân nhé.

Đầu vào: Dòng đầu tiên là số nguyên dương N. N dòng tiếp theo, mỗi dòng gồm 2 số nguyên T[i] và D[i] cho biết thời điểm đến của bệnh nhân thứ i và thời gian cần thiết để bác sĩ khám xong cho bệnh nhân này.

Ràng buộc:

1 <= N <= 100000

1 <= T[i], D[i] <= 1000000

Đầu ra:

In ra một số nguyên duy nhất là thời điểm bác sĩ khám xong cho bệnh nhân cuối cùng.

Ví dụ:

Input:

4
8 3
1 4
9 5
3 2

Output:

16

Cho 3 điểm A, B, C của tam giác và điểm M. Kiểm tra M có nằm trong hoặc nằm trên cạnh tam giác không.

Input:

4 dòng chứa tọa độ của A, B, C, M (mỗi dòng 2 số thực).

Output:

In "YES" nếu nằm trong/trên cạnh, ngược lại in "NO".

Ràng buộc:

Tọa độ x, y của các điểm là các số thực thỏa mãn: -10^6 <= x, y <= 10^6.

Dữ liệu đầu vào luôn đảm bảo 3 điểm A, B, C không thẳng hàng (tạo thành một tam giác hợp lệ).

Ví dụ

Input:

0 0 
4 0 
0 4 
1 1

Output:

YES

Hệ thống máy chủ của trường nhận được các lượt truy cập từ nhiều tài khoản khác nhau. Mỗi tài khoản được cấp một mã số nguyên dương. Ban đầu, danh sách mã truy cập an toàn là rỗng. Trong quá trình hoạt động, hệ thống sẽ nhận được Q truy vấn thuộc một trong ba loại sau:

Loại 1 (1 X): Thêm mã số X vào danh sách an toàn. Nếu X đã có trong danh sách, bỏ qua.

Loại 2 (2 X): Kiểm tra xem mã X có trong danh sách an toàn hay không.

Loại 3 (3 X): Tìm mã số an toàn nhỏ nhất nhưng lớn hơn X đang có trong hệ thống (nhằm mục đích cấp phát mã số dự phòng).

Yêu cầu: Viết chương trình xử lý Q truy vấn trên.

Đầu vào:

Dòng đầu tiên chứa số nguyên dương Q (1 <= Q <= 10^5) là số lượng truy vấn.

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên Loại (1, 2, hoặc 3) và X (1 <= X <= 10^9) cách nhau bởi khoảng trắng.

Đầu ra:

Với mỗi truy vấn loại 2: In ra YES nếu mã X tồn tại, ngược lại in ra NO.

Với mỗi truy vấn loại 3: In ra mã số tìm được. Nếu không có mã nào thỏa mãn, in ra -1. (Mỗi kết quả in trên một dòng).

Ví dụ:

Input:

7
1 5
1 10
2 5
2 8
1 8
3 5
3 15

Output:

YES
NO
8
-1

Giải thích ví dụ:

Lệnh 1 5: Thêm 5 vào danh sách. (Danh sách: {5})

Lệnh 1 10: Thêm 10 vào danh sách. (Danh sách: {5, 10})

Lệnh 2 5: 5 có trong danh sách -> YES.

Lệnh 2 8: 8 chưa có trong danh sách -> NO.

Lệnh 1 8: Thêm 8 vào danh sách. (Danh sách: {5, 8, 10})

Lệnh 3 5: Số nhỏ nhất trong danh sách lớn hơn 5 là 8 -> 8.

Lệnh 3 15: Không có số nào trong danh sách lớn hơn 15 -> -1.