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

Số nguyên tố là số nguyên lớn hơn ~1~ gồm đúng hai ước là ~1~ và chính nó. Số nửa nguyên tố là số có số lượng ước nguyên dương của nó là một số nguyên tố.

Cho hai số nguyên dương ~a~, ~b~, hãy đếm số lượng số nửa nguyên tố trong đoạn ~[a, b]~.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~1 \le T \le 10^6~) --- số bộ dữ liệu.

~T~ dòng sau, mỗi dòng chứa hai số nguyên dương ~a~, ~b~ (~1 \le a \le b \le 10^6~).

Output

Gồm ~T~ dòng, mỗi dòng chứa kết quả của bộ dữ liệu tương ứng.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~1 \le a \le b \le 10^3~; ~T \le 10^3~.
• Subtask ~2~ (~40\%~ số điểm): ~T \le 10^2~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

2
6 9
100 100

Output 1

2
0

Trên mặt phẳng toạ độ Oxy, bạn nhận được một hình vuông với cạnh song song với trục toạ độ, có góc trái dưới là ~(0, 0)~ và góc phải trên là ~(n, n)~. Hãy đếm xem có bao nhiêu điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Khoảng cách Manhattan giữa hai điểm ~(x, y)~ và ~(u, v)~ được tính bằng ~|x - u| + |y - v|~.

Input

Gồm một dòng duy nhất chứa bốn số nguyên ~n~, ~x_0~, ~y_0~, ~k~ (~1 \le n, k \le 10^{18}~; ~1 \le x_0, y_0 \le n~).

Output

In ra một số nguyên là số điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~n \le 10^3~.
• Subtask ~2~ (~30\%~ số điểm): ~k \le 10^5~.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input

4 1 1 2

Output

6

Ở một vương quốc nọ có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Mạng lưới giao thông của vương quốc gồm ~m~ con đường, con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với độ dài đúng bằng ~1~ ki-lô-mét.

Có ~k~ dự án nhà máy điện đang được triển khai, dự án thứ ~j~ sẽ xây một nhà máy điện đặt tại thành phố ~p_j~, cung cấp điện cho tất cả các thành phố nằm trong bán kính ~r_j~ ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng ~0~). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \le n, m \le 2 \times 10^5~; ~0 \le k \le 5 \times 10^5~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~) mô tả con đường thứ ~i~.

~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j~, ~r_j~ (~1 \le p_j \le n~; ~0 \le r_j \le 10^9~) mô tả dự án thứ ~j~.

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm ~n~ kí tự, kí tự thứ ~i~ bằng "1" nếu thành phố thứ ~i~ đã được cấp điện, ngược lại kí tự thứ ~i~ bằng "0" nếu thành phố thứ ~i~ chưa được cấp điện.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~r_1 = r_2 = \dots = r_{k - 1} = r_k~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
6 0
3 1

Output 2

101111

Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~, ~r~. Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy ~a_l, a_{l+1}, \dots, a_r~ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.

Input

Dòng đầu chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 5 \times 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).

~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~, ~r_i~ (~1 \le l_i \le r_i \le n~) mô tả truy vấn thứ ~i~.

Output

In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên là kết quả cho truy vấn thứ ~i~.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, q \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i \le 10~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

5 3
1 3 1 2 2
1 5
1 2
3 5

Output 1

0
1
1

Input 2

6 4
1 3 4 6 3 5
1 2
3 6
2 5
4 4

Output 2

1
3
3
0