Cho ~Q~ truy vấn, mỗi truy vấn gồm ~2~ số nguyên ~a, b~, cần in ra ~2~ số ~x, y~ sao cho ~x + y~ là số dương nhỏ nhất thỏa mãn ~\frac{x}{y} = \frac{a}{b}~, nếu không tồn tại cặp ~x, y~ thỏa mãn thì in ra ~2~ số ~0~.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ là số truy vấn ~(1 \leq Q \leq 10^5)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a, b~ miêu tả một truy vấn ~(\lvert a \rvert, \lvert b \rvert \leq 10^{18}, b \neq 0)~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra cặp số ~x, y~ thỏa mãn yêu cầu hoặc in ra ~2~ số ~0~ nếu không tồn tại cặp số thỏa mãn.

Sample Input 1

2
4 6
5 -4

Sample Output 1

2 3
5 -4

Sample Input 2

2
0 1
-5 5

Sample Output 2

0 1
0 0

Cho dãy ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy liên tiếp của dãy ~A~ gồm đúng ~K~ phần tử (hai dãy không được phép giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~, ~K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~.

• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output

• In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.

Scoring

Sample Input 1

5 2
1 3 2 1 8

Sample Output 1

5

Notes

Đáp án lớn nhất có thể đạt được là chọn 2 đoạn ~[1, 2]~ và đoạn ~[3, 4]~. ~|(1 + 3) - (1 + 8)|~ = 5

Trong khi đi hội xuân, HoBinh đã gặp một trò chơi khá là hóc búa. Quản trò có ~N~ bóng đèn. Mỗi bóng đèn có ~2~ giá trị tương ứng là ~A_i~ và ~B_i~. Lúc đầu, mọi chiếc đèn đều tắt. Ở mỗi lượt, HoBinh có thể bật lên ~1~ bóng đèn và nó sẽ bật đến hết trò chơi. Sau ~A_i~ lượt, bóng đèn thứ ~i~ được quản trò vô hiệu hóa và không thể bật được nữa. Sau một số lượt, chắn chắc mọi bóng đèn đều bị vô hiệu hóa hoặc là được bật. Khi này, trò chơi kết thúc. Điểm của Hobinh khi trò chơi kết thúc là tổng giá trị ~B~ của các bóng đèn được bật.

Sau khi nghe đề bài, HoBinh biết là anh ấy có thể tìm được số điểm cao nhất để được giải lớn nhất. Nhưng sau khi choke VOI, anh ấy đã quá chán với việc suy nghĩ nên đã nhờ bạn giúp anh ấy tìm số lượng điểm cao nhất có thể.

Input

• Dòng đầu tiên gồm ~1~ số nguyên dương ~N~. ~(1\le N \le 2*10^5)~

• Dòng thứ hai gồm ~N~ số là dãy ~A~. ~(1 \le A_i \le 10^9)~

• Dòng thứ ba gồm ~N~ số là dãy ~B~. ~(1\le B_i \le 10^9)~

Output

• Gồm một dòng là số điểm cao nhất mà HoBinh có thế lấy được

Scoring

Sample Input 1

5
1 2 2 2 3
4 9 5 1 10

Sample Output 1

24

Notes

Ta sẽ bật bóng đèn thứ ~2~ ở thời điểm ~1~, bóng đèn thứ ~3~ ở thời điểm ~2~ và bóng đèn thứ ~5~ ở thời điểm ~3~ để được ~9+5+10=24~ điểm.

Tại thành phố VNOI, một dự án mới đang hình thành một khu vực với ~n~ điểm tham quan sắp được xây dựng. Những điểm tham quan này bao gồm mọi thứ từ bảo tàng nghệ thuật đến công viên giải trí, nhưng hiện tại, chưa có lộ trình nào để tham quan những điểm này một cách thuận lợi.

Với vai trò là nhà thiết kế, bạn được giao nhiệm vụ quyết định một đường đi sao cho mọi người có thể dễ dàng di chuyển giữa các điểm tham quan một cách thuận tiện nhất. Mục tiêu là tạo ra một trải nghiệm du lịch độc đáo và thoải mái cho cả cư dân và du khách.

Thành phố VNOI có thể coi như là một lưới ô vuông. Tọa độ ô ~(i, j)~ biểu thị cho ô vuông ở hàng ~i + 1~ từ trên xuống và cột ~j + 1~ từ trái sang. Tại mỗi bước, ta có thể di chuyển sang các ô kề cạnh với ô hiện tại. Đường đi của bạn phải thỏa mãn các yếu tố sau:

• Đường đi bắt đầu từ ô ~(0, 0)~.

• Đường đi qua tất cả ~n~ điểm tham quan, mỗi điểm ít nhất một lần.

• Để tăng mức độ hấp dẫn, điểm tham quan ở ô ~(x_i, y_i)~ phải được đi qua trước điểm tham quan ở ô ~(x_j, y_j)~ nếu ~\max(x_i, y_i) < \max(x_j, y_j)~ với ~1 \le i, j \le n~.

• Tổng số bước di chuyển là ít nhất.

Yêu cầu: Cho tọa độ của ~n~ điểm tham quan. Bạn hãy tìm và in ra tổng số bước di chuyển ít nhất.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~  – số lượng điểm tham quan trong thành phố (~n \le 5 \cdot 10^5~).

~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~x_i~ và ~y_i~  – tọa độ của điểm tham quan thứ ~i~ trong thành phố (~0 \le x_i, y_i \le 10^9~).

Output

In ra một số nguyên là tổng số bước di chuyển ít nhất.

Scoring

Sample Input 1

4
0 3
4 4
2 3
3 0

Sample Output 1

14

Sample Input 2

5
3 4
3 0
0 2
1 0
0 4

Sample Output 2

16

Notes

Giải thích ví dụ:

Ở ví dụ ~1~, một trong các đường đi tối ưu là:

Ở ví dụ ~2~, một trong các đường đi tối ưu là:

Đất nước Alpha bao gồm ~n~ thành phố. Hiện tại, các thành phố được đánh số từ ~1~ đến ~n~, ở thành phố thứ ~i~ đang có dân số là ~a_i~.

Sắp tới, để cải cách lại đất nước, nhà vua quyết định sẽ hợp nhất một số thành phố lại với nhau. Các đại thần đã dâng lên nhà vua ~m~ đề xuất, trong đề xuất thứ ~i~, hai thành phố ~x_i~ và ~y_i~ sẽ được hợp nhất lại với nhau.

Sau khi nhận được đề xuất của các vị đại thần, nhà vua lập ra ~q~ kế hoạch, trong kế hoạch thứ ~i~, những lời đề xuất của các vị đại thần từ ~l_i~ đến ~r_i~ sẽ được chấp nhận. Để đánh giá độ hiệu quả của một kế hoạch, nhà vua muốn biết rằng sau khi sát nhập, thành phố có dân số nhiều nhất là bao nhiêu.

Với tư cách là tân trạng nguyên của đất nước Alpha, nhà vua đã giao cho bạn công việc khó nhằn này. Bạn hãy giúp nhà vua đánh giá độ hiệu quả của các kế hoạch hoặc bị tr...

Input

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

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

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ (~1\le x_i, y_i \le n~ ) — đề xuất của đại thần ~i~ .

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i, r_i~ (~1\le l_i, r_i \le m~ ) — kế hoạch thứ ~i~ của nhà vua.

Output

Với mỗi kế hoạch, in ra dân số lớn nhất của một thành phố sau khi thực hiện kế hoạch trên một dòng.

Scoring

Sample Input 1

6 7 4
6 4 2 7 1 13
5 3
2 5
2 3
1 2
1 6
4 3
5 4
1 3
5 7
1 4
6 7

Sample Output 1

13
19
13
13

Sample Input 2

2 1 1
1 1
1 2
1 1

Sample Output 2

2

Trong một khu rừng nọ ở vương quốc Alpha, có một chú thỏ tên là Rabbit sở hữu một mảnh đất rất lớn và màu mỡ, có thể trồng được mọi loại cây trên này. Do rất thích ăn Carrot, thỏ ta quyết định chỉ trồng carrot trên khu vườn này. Rabbit đã kiếm được ~m~ loại hạt giống khác nhau, và muốn trồng cả ~m~ loại hạt giống này.

Mảnh đất có thể coi như hệ tọa độ Descarte ~Oxy~ vô hạn với nhà của Rabbit nằm ở tọa độ ~O(0,0)~. Một điểm trên mảnh đất có tọa độ ~(x, y)~ nếu nó cách nhà của Rabbit độ dài ~x~ theo trục ~Ox~ và ~y~ theo trục ~Oy~ (Lưu ý ~x~ và ~y~ có thể âm). Với hạt giống carrot thứ ~i~, Rabbit quyết định trồng nó ở điểm ~(x_{c_i}, y_{c_i})~ trên mảnh đất.

Để bảo vệ khu vườn của mình khỏi sự phá hoại của kẻ khác hoặc sự tàn phá của thời tiết, Rabbit quyết định sẽ đóng thêm ~n~ chiếc cọc ở ~n~ vị trí khác nhau trên khu vườn. Theo tính toán của mình, Rabbit sẽ đóng chiếc cọc thứ ~i~ vào điểm có tọa độ ~(x_{s_i}, y_{s_i})~. Khi đóng cọc như thế này, Rabbit biết rằng ~1~ củ carrot sẽ an toàn và cho năng suất cao nhất khi được nằm hoàn toàn trong ~1~ đa giác không tự cắt tạo bởi một tập hợp các cọc trong ~n~ chiếc cọc đó.

Ví dụ các đa giác ~ABCD~ trong hai hình dưới đây là một đa giác không tự cắt:

Còn đa giác ~ABCD~ trong hình dưới đây thì không:

Do đã mất quá nhiều thời gian để tìm kiếm và trồng carrot, Rabbit không có đủ thời gian để tìm đủ ~n~ chiếc cọc. Do đó, thỏ đã tính toán ~q~ kế hoạch như sau.

• Với mỗi kế hoạch, Rabbit chọn ra ~k~ trong ~n~ vị trí để đặt chiếc cọc.
• Với ~k~ chiếc cọc được đóng như trên, số lượng carrot được bảo vệ và cho năng suất tốt nhất là bao nhiêu?

Lưu ý rằng, để carrot có thể phát triển tốt nhất có thể, sẽ không có củ carrot nào được trồng cùng vị trí với ~1~ chiếc cọc hay ~1~ củ carrot khác, đồng thời không có ~2~ chiếc cọc nào được đóng cùng một chỗ. Sẽ không có carrot nào thẳng hàng với ~2~ chiếc cọc. Hơn nữa, để đảm bảo an toàn, sẽ không có chiếc cọc hay carrot nào được trồng ở nhà thỏ, và không có ~2~ chiếc cọc nào trong ~n~ chiếc cọc được đóng thẳng hàng với nhà thỏ, đồng thời không có carrot nào nằm trên cùng ~1~ đường thẳng với ~1~ chiếc cọc và nhà thỏ.

Input

Dòng thứ nhất gồm số nguyên dương ~n~ ~(1 \le n \le 200)~ là số lượng chiếc cọc Rabbit muốn đóng trên mảnh đất.

~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i, y_i~ ~(|x_i|, |y_i| \le 10^9)~ miêu tả tọa độ ~(x_i, y_i)~ của chiếc cọc thứ ~i~.

Dòng tiếp theo gồm số nguyên dương ~m~ là số lượng carrot Rabbit muốn trồng ~(1 \le m \le 1000)~.

~m~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i, y_i~ ~(|x_i|, |y_i| \le 10^9)~ miêu tả tọa độ ~(x_i, y_i)~ của carrot thứ ~i~.

Dòng tiếp theo gồm số nguyên dương ~q~ ~(1 \le q \le 2 * 10^5)~ miêu tả số lượng kế hoạch của Rabbit.

~q~ dòng tiếp theo, mỗi dòng gồm số nguyên dương ~k~ miêu tả số chiếc cọc Rabbit sẽ dùng trong ~n~ chiếc cọc trên, tiếp theo là ~k~ số nguyên dương ~x_1, x_2, x_3, \dots, x_k~ miêu tả chỉ số các chiếc cọc mà Rabbit sẽ chọn ~(3 \le k \le n, 1 \le x_i \le n)~.

Gọi ~T~ là tổng của ~k~ trong mọi truy vấn, dữ lệu đảm bảo ~T~ không quá ~2 * 10^6~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án của kế hoạch thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

1
1
1