Cho N điêm trên mặt phẳng tọa độ, mỗi điểm có tọa độ nguyên. Hãy tìm cặp điểm có khoảng cách lớn nhất.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím):

• Dòng đầu tiên: số nguyên dương N là số lượng điểm.

• N dòng tiếp theo: mỗi dòng gồm 2 số nguyên x y là tọa độ của điểm thứ i (i từ 1 đến N).

Kết quả: ghi ra thiết bị chuẩn (màn hình): Một dòng gồm 2 số nguyên là chỉ số của cặp điểm xa nhau nhất (chỉ số nhỏ in trước). Nếu có nhiều cặp điểm cùng đạt khoảng cách lớn nhất, hãy chọn cặp có tổng chỉ số nhỏ nhất.

Ràng buộc:

• 40% test: N ≤ 10, tọa độ các điêm có giá trị tuyệt đối ≤ 100.

• 60% test: N ≤ 100, tọa độ các điểm có giá trị tuyệt đối ≤ 10^4.

Input:

5
0 0
0 5
5 5
1 3
5 0

Output:

1 3

Hai cặp điểm cùng đạt khoảng cách lớn nhất:

• Cặp (1, 3): điểm 1 là (0, 0), điểm 3 là (5, 5)

• Cặp (2,5): điểm 2 là (0, 5), điểm 5 là (5, 0)

Tổng chỉ số cặp (1, 3) = 4, tổng chỉ số cặp (2, 5) = 7. Do 4 < 7, kết quả in ra là 1 3.

Một số nguyên dương được gọi là "số đẹp" nếu số đó chia hết cho số lượng ước nguyên dương của nó. Ví dụ số 40 có 8 ước nguyên dương là: 1, 2, 4, 5, 8, 10, 20, 40 và 40 chia hết cho 8 nên 40 là "số đẹp".

Yêu cầu: Hãy kiểm tra một số nguyên dương cho trước có là "số đẹp" hay không.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím):

• Dòng đầu tiên chứa số nguyên dương N.

• N dòng tiếp theo, mỗi dòng ghi một số nguyên dương cần kiếm tra.

Kết quả: ghi ra thiết bị chuẩn (màn hình) gồm N dòng, mỗi dòng ghi số 1 nếu số nguyên tương ứng trong dữ liệu đọc vào là số "số đẹp", ngược lại thì ghi số 0.

Ràng buộc:

• Có 40% số test của bài có N = 1, các số nguyên có giá trị không quá 10^4;

• Có 60% số test còn lại của bài có N < 100, các số nguyên có giá trị không quá 10^9.

Input 01:

1
40

Output 01:

1

Input 01:

2
5
8

Output 02:

0
1

Cho dãy gồm n số nguyên dương và một số nguyên dương k, k ≤ n, các số trong dãy không vượt quá 10^5. Hãy tìm số hạng lớn thứ k của dãy. Ví dụ dãy 6 số nguyên 6, 3, 1, 2, 3, 7: nếu k = 1 cho kết quả là 7, k = 2 cho kết quả là 6,..... k = 5 cho kết quả là 1, k = 6 thì không có số lớn thứ 6.

Yêu cầu: Hãy tìm số lớn thứ k trong dãy.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím):

• Dòng đầu tiên ghi số nguyên dương n

• Dòng thứ hai ghi số k

• Mỗi dòng còn lại trong số n dòng tiếp theo ghi lần lượt từng số của dãy số.

Kết quả: Ghi ra thiết bị chuẩn (màn hình) số lớn thứ k tìm được, nếu không có số như vậy thì ghi 0.

Ràng buộc:

• Có 50% số test của bài có n ≤ 10^3;

• Có 50% số test còn lại của bài có n ≤ 10^5.

Input 01:

6
2
6
3
1
2
3
7

Output 01:

6

Input 02:

6
8
6
3
1
2
3
7

Output 02:

0

Ma trận N x N ban đầu bằng 0.

Thực hiện Q thao tác cập nhật cộng 1 vào vùng (r1, c1, r2, c2).

Sau khi cập nhật, những ô có giá trị > 0 được gọi là "ô đen", giá trị 0 là "ô trắng".

Hãy tìm diện tích của hình vuông "ô đen" lớn nhất (hình vuông chứa toàn các ô có giá trị > 0).

Gợi ý: Dùng Mảng hiệu để xác định ô đen/trắng (0/1). Sau đó dùng Quy Hoạch Động cơ bản (bài toán Maximal Square) để tìm hình vuông.

Input:

• N, Q.

• Q dòng: r1, c1, r2, c2.

Output:

• Diện tích hình vuông ô đen lớn nhất (Cạnh * Cạnh).

Ví dụ

Input:

3 2
1 1 2 2
2 2 3 3

Output:

4