Trong mặt phẳng tọa độ Oxy, hệ thống radar bắt được tín hiệu của 4 vật thể lạ tại 4 điểm phân biệt. Sở chỉ huy nghi ngờ chúng là 4 góc của một trạm vũ trụ tàng hình có hình dạng là một hình vuông hoàn hảo. Bạn được cung cấp tọa độ (x, y) của 4 điểm này, hãy kiểm tra xem chúng có thực sự tạo thành một hình vuông hay không.

Input: Gồm 4 dòng, mỗi dòng chứa 2 số nguyên x, y là tọa độ của một điểm (-10^4 <= x, y <= 10^4).

Output: In ra YES nếu 4 điểm tạo thành hình vuông, ngược lại in NO.

Ví dụ:

Input:

0 0
0 1
1 0
1 1

Output:

YES

Là một freelancer, bạn nhận được danh sách N dự án. Dự án thứ i mang lại thù lao Pi nhưng bắt buộc phải hoàn thành trước thời điểm Di (nếu thời điểm hiện tại t > D_i thì không thể nhận). Biết rằng mỗi dự án đều tốn đúng 1 đơn vị thời gian để hoàn thành, và bạn chỉ có thể làm 1 dự án tại 1 thời điểm (bắt đầu từ thời điểm 1). Hãy chọn ra các dự án để làm sao cho tổng thù lao thu được là lớn nhất.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng gồm 2 số nguyên Di, Pi (1 <= Di <= 10^5, 1 <= Pi <= 10^4).

Output: Tổng thù lao lớn nhất.

Ví dụ:

Input 01:

4
4 20
1 10
1 40
1 30

Output 01:

60

(Giải thích: Chọn dự án thù lao 40 làm vào thời điểm 1, dự án thù lao 20 làm vào thời điểm 2. Không thể chọn cả dự án 40 và 30 vì chúng đều có deadline là 1).

Input 02:

3
1 10
2 30
2 60

Output 02:

90

Cho mảng A gồm N số nguyên. Một đoạn con liên tiếp của mảng được coi là "đoạn triệt tiêu" nếu tổng XOR của tất cả các phần tử trong đoạn đó bằng 0. Bạn hãy đếm xem trong mảng A có tất cả bao nhiêu "đoạn triệt tiêu".

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^9).

Output: Số lượng đoạn con có tổng XOR bằng 0.

Ví dụ:

Input:

5
3 0 2 2 3

Output:

4

(Giải thích: Các đoạn là [0], [2, 2], [3, 0, 2, 2, 3], và [0, 2, 2]).

Một dãy số được gọi là "dãy núi" nếu nó tăng ngặt lên đến một đỉnh rồi giảm ngặt xuống (ví dụ 1 3 5 4 2). Cho dãy A gồm N số nguyên, bạn hãy tìm cách xóa đi một số phần tử để các phần tử còn lại giữ nguyên thứ tự tạo thành một "dãy núi" dài nhất. In ra độ dài lớn nhất đó.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Độ dài của dãy con Bitonic dài nhất.

Ví dụ:

Input:

6
1 5 2 4 2 1

Output:

5

(Giải thích: Dãy con chọn là 1 5 4 2 1).