Cho hai điểm ~A~, ~B~ trên trục Ox có toạ độ nguyên. Tìm hai điểm ~X~, ~Y~ có toạ độ nguyên trên trục Ox sao cho hai điểm này chia đoạn thằng ~AB~ thành ba phần có độ dài bằng nhau. Nếu không tồn tại hai điểm như trên, in ra ~-1~.

Input

Gồm một dòng duy nhất chứa hai số nguyên ~a~, ~b~ (~1 \le a < b \le 10^9~) lần lượt mô tả toạ độ của điểm ~A~ và toạ độ của điểm ~B~.

Output

Nếu tồn tại hai điểm ~X~, ~Y~ như trên, in ra hai số nguyên ~x~, ~y~ (~x \le y~) lần lượt là toạ độ của hai điểm ~X~, ~Y~ tìm được, ngược lại in ra ~-1~.

Example

Input 1

1 4

Output 1

2 3

Input 2

2 6

Output 2

-1

Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của hai số tự nhiên liên tiếp hay không.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~1 \leq N \le 10^9~)

Output

In ra YES nếu ~N~ là tổng của hai số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

5

Output:

YES

Note:

Do ~5 = 2 + 3~ nên ~5~ là tổng của hai số tự nhiên liên tiếp.

Sample Test 2

Input:

6

Output:

NO

Sample Test 3

Input:

11

Output:

YES

Đây là phiên bản khó hơn của bài PA094. Điểm khác biệt duy nhất giữa hai bài là giới hạn của ~n~ và đầu vào/ra dữ liệu.

Cho ~n~ điểm trên mặt phẳng Descartes, điểm ~A_i~ có toạ độ ~(x_i, y_i)~. Hãy tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong ~n~ điểm đã cho.

Khoảng cách Manhattan giữa hai điểm ~A(x_A, y_A)~ và ~B(x_B, y_B)~ có giá trị là ~|x_A - x_B| + |y_A - y_B|~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - số lượng điểm (~2 \leq n \leq 10^5~).
• ~n~ dòng tiếp theo, một dòng chứa hai số nguyên ~x_i~ và ~y_i~ mô tả toạ độ của điểm ~A_i~ (~|x_i|, |y_i| \leq 10^9~).

Output

In ra khoảng cách Manhattan lớn nhất tìm được.

Sample Test

Input:

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

Output:

9

Note: Khoảng cách giữa điểm ~A_3~ và ~A_4~ bằng ~9~ là khoảng cách lớn nhất.

Bạn được cho hai số nguyên dương ~N~ và ~X~. Hãy đếm số lượng số tự nhiên có ~N~ chữ số mà chia hết cho ~2^X~.

Dữ liệu vào từ tệp văn bản: CHIAHET2.INP

Bạn sẽ phải trả lời bài toán trên ~T~ lần:

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T \le 10^3~).
• ~T~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~N, X~ ~(1 \le N \le 18, 0 \le X \le 60)~ là dữ liệu của câu hỏi thứ ~i~.

Kết quả ghi ra tệp văn bản: CHIAHET2.OUT

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bài toán thứ ~i~.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~T \le 10, N \le 6~.
• Subtask 2 (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2
2 4
3 3

Sample Output 1

6
112

Giải thích: Các số có ~2~ chữ số chia hết cho ~2^4~ là: ~16, 32, 48, 64, 80, 96~.

Sample Input 2

1
1 3

Sample Output 2

2

Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là tính toán trung vị của mỗi đoạn con gồm ~k~ phần tử liên tiếp, từ trái sang phải.

Trung vị là phần tử ở giữa khi các phần tử được sắp xếp. Nếu số lượng phần tử là số chẵn, có thể có hai trung vị và chúng ta giả định rằng trung vị là số nhỏ hơn trong chúng.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~k~: số lượng phần tử và kích thước của đoạn con.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ - nội dung của mảng.

Output

• In ra ~n - k + 1~ giá trị: các trung vị

Constraints

• ~1 \leq k \leq n \leq 2 \times 10^5~
• ~1 \leq a_i \leq 10^9~.

Sample Test

Input:

8 3
2 4 3 5 8 1 2 1

Output:

3 4 5 5 2 1