Trong dải ngân hà có hai ngôi sao chuyển động theo quỹ đạo vòng tròn và nằm trên cùng mặt phẳng. Cho biết tọa độ tâm và bán kính của hai quỹ đạo (hai quỹ đạo không trùng nhau), hỏi khoảng cách gần nhất và xa nhất của hai ngôi sao có thể có là bao nhiêu?

Input

Gồm hai dòng cho biết tọa độ tâm ~(x_i,y_i)~ và bán kính ~R_i~ của sao ~i~ với ~i = 1,2~. Các giá trị có trị tuyệt đối không quá ~10^4.~

Output

In ra khoảng cách gần nhất và xa nhất, làm tròn đến ~2~ chữ số thập phân.

Sample input

0 0 1
0 0 2

Sample output

1.00 3.00

Giải thích: các bạn có thể vẽ hình ra cho dễ hình dung.

Bố Tài Super Cute hôm nay lại cho các con zai yêu một bài toán vui. Bố viết một dãy ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ và đặt ra ~m~ câu hỏi. Với mỗi câu, bố cho hai số nguyên dương ~L, R~ và với từng số nguyên tố ~p~ thuộc đoạn ~[L;R]~, bố muốn tính số lượng bội của ~p~ có trong dãy đã cho, sau đó cộng hết các kết quả lại với nhau. Bạn hãy đóng vai làm con zai yêu của bố Tài super cute để giải quyết bài toán này nhé.

Input

• Dòng đầu tiên chứa số nguyên ~n~ với ~1≤ n ≤ 10^5.~
• Dòng thứ 2 chứa ~n~ số nguyên dương ~x_1, x_2, …, x_n~ với ~2 ≤ x_i ≤ 10^7~
• Dòng thứ 3 chứa số nguyên ~m~ với ~1 ≤ m ≤ 50000~. Mỗi dòng ~i~ trong ~m~ dòng sau chứa 2 số nguyên ngăn cách bởi 1 dấu cách ~L, R~ với ~2 ≤ L ≤ R ≤ 2.10^9~.

Output

• Gồm m dòng, mỗi dòng 1 số nguyên là câu trả lời cho một truy vấn.

Sample input

6
5 5 7 10 14 15
3
2 11
3 12
4 4

Sample output

9
7
0

Giải thích: trong câu hỏi 1, ta thấy có các số nguyên tố ~2,3,5,7,11~ trong đoạn đã cho. Ta tính được lần lượt có: ~2,1,4,2,0~ bội của chúng trong dãy, vì thế tổng cần tìm là ~9~. Tương tự với các câu hỏi khác.

Subtask

• Sub1: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^3.~
• Sub2: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^6.~
• Sub3: 40% test có ràng buộc như đề bài đã mô tả.

Sau mùa code camp ở Tà Nung đáng nhớ, anh Trung đã về quê của mình trồng các cây thông. Bằng phương pháp đặc biệt, anh có thể trồng được các cây xứ lạnh đó ở vùng sông nước, để cứ mỗi chiều ra ngồi bên hàng thông để ngắm hoàng hôn và chill chill code. Tuy nhiên, một ngày nọ, có một Phú ông từ phương xa đến mua mua lại hàng thông với giá cao, đem về làm đồ nội thất, vì gỗ thông rất chắc chắn. Phú ông muốn mua một dãy liên tiếp các cây thông có chiều cao trung bình là ~k~, trong đó hàng thông của anh Trung thì có ~n~ cây với chiều cao ~h_1, h_2, ..., h_n~. Anh Trung cũng không ngại bán, vì bán xong thì trồng lại cũng không khó. Vì thế anh muốn chọn một dãy dài nhất có thể các cây thông của mình để bán cho Phú ông, hỏi dãy đó sẽ bắt đầu và kết thúc tại cây nào? Bạn hãy giúp anh Trung tính toán nhé: nếu không có cách nào bán được thì in ra ~0~, còn nếu có thì in ra vị trí bắt đầu ~L~ và độ dài dài nhất đó (nếu có nhiều cách chọn thì in ra ~L~ nhỏ nhất).

Input

Dòng đầu tiên gồm số nguyên ~n,k~ với ~1 \le n \le 10^5~ và ~1 \le k \le 10^9.~

Trong cac dòng tiếp theo là độ dài của các cây thông, giá trị nguyên dương không quá ~10^9.~

Output

Đáp số của bài toán: vị trí ~L~ và độ dài.

Sample input

4 5
2
4
5
6

Sample output

2 3

Subtasks

• Sub1 (40%): ~1≤ N ≤ 500~
• Sub2 (30%): ~1≤ N ≤ 5000~
• Sub3 (30%): ~1≤ N ≤ 10^5.~

Sau một ngày làm việc vất vả, anh Long sẽ thưởng cho mình bằng những bữa ăn với những chùm nho mẫu đơn ngon lành. Anh ta có ~n~ trái nho được nối với nhau qua ~n-1~ cành, hai trái nho bất kì luôn được nối với nhau qua chuỗi những cành. Long sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt ~2~ cành cây bất kì để có được ~3~ nhánh nho, mỗi nhánh cho mỗi bữa.

Tuy nhiên anh Long không muốn bất kì bữa ăn nào quá ngọt ngào nên anh ấy quyết định cắt sao cho độ chênh lệch giữa nhánh có nhiều nho nhất và ít nho nhất là nhỏ nhất có thể. Bạn phải giúp anh ấy tìm độ chênh lệch đó.

Input

• Dòng đầu chứa số nguyên ~n~ là số lượng nho. Các trái được đánh số từ ~1 \to n~ với ~1 \le n \le 2.10^5 ).~
• Mỗi dòng trong ~n-1~ dòng còn lại gồm ~2~ số nguyên ~x~ và ~y~ với ~1 ≤ x,y ≤ n~ số hiệu 2 trái nho nối trực tiếp với nhau.

Output

In ra độ chênh lệch tối thiểu giữa đùm có nhiều nho nhất và ít nho nhất.

Sample input 1

4
1 2
2 3
3 4

Sample output 1

1

Sample input 2

6
1 2
1 3
3 4
3 5
5 6

Sample output 2

0