Huấn luyện viên Bình quản lý ~N~ đội tuyển thể thao, đội thứ ~i~ có hai thông số: Sức bền ~m_i~ và sức mạnh ~v_i~. Để đánh giá toàn diện, ông Bình tính tổng sức ~T_i~ của mỗi đội là ~m_i + v_i~. Sau khi tính tất cả các giá trị ~T_i~, ông muốn biết chênh lệch giữa đội có tổng sức lớn nhất và đội có tổng sức bé nhất.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~ (~2 \le N \le 10^5~) là số lượng đội tuyển thể thao.
• Trong ~N~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~m_i~ và ~v_i~ (~0 \le m_i, v_i \le 10^9~), lần lượt là thông số sức bền và sức mạnh của mỗi đội tuyển.

Output

In ra một số nguyên duy nhất là kết quả của bài toán

Giới hạn

• 50% số điểm: ~N \le 100~
• 50% số điểm: ~N \le 10^5~

Sample Input

8
4 6
1 3
2 5
4 2
3 3
7 2
8 1
7 8

Sample Output

11

Giải thích

Có 8 đội, với tổng sức lần lượt là 4 + 6 = 10, 1 + 3 = 4, 2 + 5 = 7, 4 + 2 = 6, 3 + 3 = 6, 7 + 2 = 9, 8 + 1 = 9 và 7 + 8 = 15 nên chênh lệch là 15 - 4 = 11

Cho số nguyên dương ~N~. Hãy tính số dư của ~2^{3^N}~ khi chia cho 5.

Input

Số nguyên dương ~N~ ~(1 \le N \le 10^9)~

Output

In ra một số số nguyên duy nhất là kết quả của bài toán

Sample Input

2

Sample Output

2

Giải thích: ~3^2 = 9~, ~2^9 = 512~, 512 chia 5 dư 2.

Cho một dãy ~N~ số nguyên: ~a_0, a_1, ..., a_n~. Khoảng cách giữa hai số ~a_i~ và ~a_j~ (~0 \le i, j \le N-1, i≠j~) được định nghĩa là ~|i - j|~. TÌm khoảng cách ngắn nhất giữa hai số bằng nhau trong dãy, nếu không có hai số nào bằng nhau, in ra ~-1~.

Input

• Dòng đầu tiên ghi một số nguyên dương ~N~ (~2 \le N \le 10^5~)
• Dòng thứ hai ghi ~N~ số nguyên ~a_0, a_1, ...., a_{n-1}~ (~-10^9 \le a_i \le 10^9~)

Output

In ra một số nguyên duy nhất là kết quả của bài toán

Giới hạn

• 80% số điểm: ~N \le 10^3~ và ~-10^5 \le a_i \le 10^5~ với ~0 \le i \le N-1~
• 20% số điểm: Không có ràng buộc gì thêm.

Sample Input

5
7 2 3 2 7

Sample Output

2

Giải thích

Dãy [7 2 3 2 7] có hai cặp số bằng nhau:

• ~7~ ở vị trí ~0~ và ~4~, khoảng cách ~4~
• ~2~ ở vị trí ~1~ và ~2~, khoảng cách ~2~

Nên kết quả của bài toán là ~2~