Tay săn ảnh trẻ tuổi nhưng đầy triển vọng ABC rất muốn trở nên nổi tiếng. Để làm được điều này, anh ấy muốn chụp ảnh một siêu sao mới nổi trong khi cô ấy đi dạo trên núi.

Được biết, quãng đường của ngôi sao đó trên núi gồm ~n~ đoạn. Với mỗi ~i~, đoạn đường thứ ~i~ là một khoảng nửa mở thẳng đứng có tọa độ ~x = i~ và ~y ∈ [0, hi)~.

Nếu ABC đứng ở vị trí ~j~ và người nổi tiếng ấy đứng ở vị trí ~i~, anh ta có thể chụp được cô khi và chỉ khi anh ta nhìn thấy cô, tức là ~i < j~ và với mọi ~i < k < j~, khoảng nửa mở tạo lên đoạn thứ ~k~ không được cắt đoạn ~[(i,j_i),(j,h_j)]~. ABC là một tay săn ảnh, dĩ nhiên không phải là một lập trình viên, vì vậy anh muốn bạn xác định khoảng cách tối đa mà anh ấy có thể chụp được ảnh ngôi sao nổi tiếng trên, tức là tìm là giá trị lớn nhất của ~j - i~ trên tất cả các cặp ~(i, j)~ thỏa mãn điều kiện. Hãy giúp anh ấy trở nên nổi tiếng!

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng đoạn.
• Dòng thứ hai gồm ~n~ số nguyên ~h_1,h_2,...,h_n~.

Output

• In ra khoảng cách lớn nhất cần tìm.

Constraints

• ~3 \le n \le 10^5~.
• ~1 \le h_i \le 10^9~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

7
3 2 5 3 2 4 3

Sample Output 1

3

Explanation 1

Cặp ~(3,7)~ không thỏa mãn do ~FN~ giao với ~KL~. Cặp ~(3,6)~ là một cặp thỏa mãn và cho ra kết quả tốt nhất.

Hôm nay là sinh nhật ~ABC~ và ~DEF~ muốn chuẩn bị một chiếc bánh cho cô ấy. Anh ấy có ~n~ điểm ~(x_1, y_1), (x_2, y_2), …, (x_n, y_n)~ trong mặt phẳng hai chiều, và một cây nến được đặt ở một điểm trong mặt phẳng.

Số lớp của chiếc bánh là một số không âm. ~DEF~ coi độ ngon của chiếc bánh bằng với số lớp của chiếc bánh. Một lớp là một đa giác đơn với các đỉnh là một số điểm trong ~n~ điểm của ~DEF~. Với mỗi điểm của ~DEF~, nó không nhất thiết phải thuộc một lớp. Hơn nữa các lớp phải thỏa mãn các điều kiện sau:

• Với mỗi lớp, cây nến phải nằm hẳn bên trong nó
• Với mỗi điểm trong ~n~ điểm mà nằm hẳn trong một lớp, nó phải thuộc lớp khác hoặc có thể là điểm của cây nến
• Không có hai lớp nào chạm hoặc giao nhau
• Các lớp phải được chọn sao cho độ ngon của chiếc bánh là lớn nhất có thể

Bây giờ ~DEF~ tự hỏi, độ ngon của chiếc bánh phụ thuộc thế nào vào vị trí đặt nến. Bạn cần trả lời ~q~ truy vấn. Trong mỗi truy vấn, bạn được cho một điểm ~p = (x, y)~ là điểm mà ~DEF~ đặt nến và bạn cần tìm phải độ ngon của chiếc bánh

Input

• Dòng đầu gồm số nguyên dương ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i,y_i~.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x,y~ miêu tả truy vấn.

  Output

• Với mỗi truy vấn, in ra một dòng chứa số nguyên là độ ngon của bánh.

Constraints

• ~3 \le n \le 5000~.
• ~1 \le q \le 2000~.
• ~-10^9 \le x_i,y_i \le 10^9~.
• ~-10^9 \le x,y \le 10^9~.

Subtask

• ~50\%~ số điểm có ~1 \le n,q \le 200~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

6 2
0 0
6 0
3 4
2 1
4 1
3 3
6 6
3 3

Sample Output 1

0
1

Explanation 1

Trong truy vấn đầu tiên, ~p = (6, 6)~. Bánh không thể có lớp nào, nên độ ngon của nó là ~0~

Trong truy vấn thứ hai, ~p = (3, 3)~. Bánh chỉ có thể có một lớp, ví dụ là một tam giác với các đỉnh là ~(2, 1), (4, 1), (3, 4)~. Có những lựa chọn khác cho lớp này nhưng bánh không thể có nhiều hơn ~1~ lớp.

Trên hệ trục tọa độ ~OXY~, cho hai tập điểm nguyên ~A~ và ~B~ lần lượt gồm ~n~ và ~m~ điểm.

Tập điểm ~A~ gồm ~a_1,a_2,...,a_n~ và tập điểm ~B~ gồm ~b_1,b_2,...,b_m~.

Gọi ~f(i,j,k)~ là số điểm ~b_x~ nằm trong tam giác được tạo bởi ba đểm ~(a_i,a_j,a_k)~.

Tính ~\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^n f(i,j,k)~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~ ~(1 \le n,m \le 300)~;
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.
• ~m~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.

Dữ liệu đảm bảo tọa độ ~x~ của mọi điểm là phân biệt và không có bộ ba điểm nào thẳng hàng.

Output

• In ra kết quả của bài toán.

Sample Input 1

4 2
1 1
2 5
7 4
9 2
3 4
6 6

Sample Output 1

2

Subtask

• Có ~80\%~ số điểm có ~n,m \le 50~.
• Có ~20\%~ số điểm không có ràng buộc gì thêm.

Cho một đa giác lồi gồm ~n~ đỉnh, đỉnh thứ ~i~ là ~P_i~. Bạn cần chọn ra ba điểm ~a,b,c~ phân biệt theo thứ tự ngược chiều kim đồng hồ thuộc ~P~, sao cho tồn tại đúng ~k~ cạnh từ ~b~ tới ~c~ theo thứ tự ngược chiều kim đồng hồ.

Giờ ta sẽ cắt đa giác ~P~ ra với hai đoạn ~ab~, ~ac~. Gọi ~Q~ là đa giác gồm ~ab~, ~ac~ và ~k~ cạnh nằm giữa ~b~ và ~c~. Đa giác này gồm ~k+2~ cạnh.

Tìm diện tích lớn nhất có thể của đa giác ~Q~. Chú ý rằng ~ab~ và ~bc~ có thể đồng thời là một cạnh của ~P~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~x_i~ và ~y_i~ là tọa độ của điểm ~P_i~.
• Tọa độ các điểm được nhập theo thứ tự ngược chiều kim đồng hồ.

Constraints

• ~n \le 10^5~
• ~1 \le k \le n-2~

Subtask

• Subtask ~1~: ~n \le 50~ ~(40\%)~
• Subtask ~2~: ~n \le 200~ ~(30\%)~
• Subtask ~3~: Không có giới hạn gì thêm ~(30\%)~

Output

• In ra diện tích lớn nhất tìm được, lấy ~1~ chữ số sau dấu thập phân.

Sample Input 1:

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

Sample Output 1:

26.5

Sample Input 2:

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

Sample Output 2:

20.0    

Explanation :

Ví dụ ~1~ và ~2~ được minh họa qua hình vẽ sau:

Trên hệ trục tọa độ ~OXY~, cho ~n~ điểm xanh và ~m~ điểm đỏ có tọa độ nguyên.

Ta gọi các điểm thuộc tập xanh là ~b_1,b_2,...,b_n~.

Gọi các điểm tập đỏ là ~r_1,r_2,...,r_m~.

Với một tập điểm ~P = \{p_1,p_2,...,p_k\}~ trên hệ trục tọa độ ~OXY~, gọi ~S(P)~ là tập các đa giác không tự cắt sao cho các đỉnh của nó đều nằm trong tập ~P~.

Cho ~q~ truy vấn, truy vấn thứ ~i~ có dạng như sau:

• Bạn sẽ nhận được một số nguyên dương ~k~, sau đó là ~k~ số nguyên dương ~x_1,x_2,...,x_k~ khác nhau đôi một ~(1 \le x_i \le n)~. Tập chỉ số này miêu tả tập điểm ~X = \{b_{x_1},b_{x_2},...,b_{x_k}\}~.
• Hãy đếm số điểm ~r_i~ ~(1 \le i \le m)~ sao cho nó nằm hoàn toàn trong ít nhất một đa giác không tự cắt thuộc tập ~S(X)~.

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:

Quan trọng: Toàn bộ các điểm được cho đều phân biệt, không có bộ ba điểm nào thẳng hàng và cũng không có cặp điểm nào tạo thành một đường thẳng đi qua gốc tọa độ ~(0,0)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số điểm xanh.
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~b_i~ ~(1 \le n \le 200; |x_i|,|y_i| \le 10^9)~.
• Dòng tiếp theo gồm số nguyên dương ~m~ miêu tả số điểm đỏ.
• ~m~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~r_i~ ~(1 \le m \le 1000; |x_i|,|y_i| \le 10^9)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ miêu tả số truy vấn ~(1 \le q \le 2 \times 10^5)~ .
• ~q~ dòng tiếp theo, mỗi dòng gồm số nguyên dương ~k~ miêu tả số điểm trong truy vấn, tiếp theo là ~k~ số nguyên dương ~x_1,x_2,...,x_k~ miêu tả các điểm ~b_{x_1},b_{x_2},...,b_{x_k}~ ~(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ữ liệu đảm bảo ~T~ không vượt quá ~2 \times 10^6~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ in ra đáp án của truy vấn thứ ~i~.

Sample Input 1

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

Sample Output 1

1
0
2

Explanation 1

Xét hình vẽ minh họa:

Ở đây ta có điểm ~b_1,b_2,b_3,b_4,b_5,b_6~ được kí hiệu lần lượt là ~A,B,C,D,E,F~. Các điểm ~r_1,r_2,r_3~ được kí hiệu lần lượt ~G,H,I~.

• Ở truy vấn đầu tiên, ta có điểm ~H~ nằm trong tam giác ~ABC~.
• Ở truy vấn thứ hai, ta thấy không có điểm đỏ nào nằm hoàn toàn trong một đa giác không tự cắt nào trong tập điểm ~\{A,B,D,F\}~.
• Ở truy vấn thứ ba, ta có điểm ~H~ nằm trong đa giác ~CBFD~ và điểm ~G~ nằm trong đa giác ~CFDE~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,m,q \le 100~, trong mọi truy vấn thì ~k = 3~.
• Subtask ~2~ ~(25\%)~: ~n,m,q \le 100~, trong mọi truy vấn, đảm bảo rằng các điểm ~b_{x_1},b_{x_2},...,b_{x_k}~ tạo thành một đa giác lồi với các điểm theo thứ tự ngược chiều kim đồng hồ.
• Subtask ~3~ ~(30\%)~: ~q \le 5 \times 10^3~.
• Subtask ~4~ ~(25\%)~: Không có ràng buộc gì thêm.

Hôm nay bé Si làm bánh, mời những người bạn tới nhà để ăn mừng chức vô địch World Cup. Trên mặt phẳng tọa độ, chiếc bánh của bé Si được xem như là một đa giác điểm nguyên không tự cắt. Bé Rô - người bạn thân nhất của bé Si cũng tới nhà Si để ăn mừng thành tích của bạn mình.

Lúc này Rô nghĩ ra một thử thách để làm khó Si. Rô đưa ra ~q~ câu hỏi, với mỗi câu hỏi Rô sẽ đưa ra hai số nguyên ~l~ và ~r~, khi đó Rô sẽ dùng dao để cắt toàn bộ phần bánh bị giới hạn bởi hai đường thẳng ~x = l~ và ~x = r~ (có thể là không có phần bánh nào). Với mỗi câu hỏi như thế, Rô đố Si hãy tính diện tích phần bánh bị cắt ra. Lưu ý rằng mỗi câu hỏi được xem như một trường hợp riêng biệt và không ảnh hưởng đến nhau.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(3 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)~ là số đỉnh của đa giác và số truy vấn.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~ ~(|x_i|, |y_i| \leq 10^9)~ là toạ độ của đỉnh thứ ~i~. Điểm ~(x_i, y_i)~ có cạnh nối tới đỉnh ~(x_{i+1}, y_{i+1})~ với ~1 \le i < n~ và đỉnh ~(x_n, y_n)~ có cạnh nối tới đỉnh ~(x_1, y_1)~. Dữ liệu đảm bảo các đỉnh được cho lần lượt theo chiều kim đồng hồ.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ ~(-10^9 \leq l \leq r \leq 10^9)~ mô tả một truy vấn.

Output

• Gồm ~q~ dòng, mỗi dòng chứa một số thực là diện tích phần bánh bị cắt ra ứng với mỗi truy vấn.
• Đáp án của bạn được chấp nhận nếu chênh lệch tương đối không vượt quá ~10^{-6}~. Hay nói cách khác, nếu đáp án của bạn là ~a~ và đáp án của giám khảo là ~b~, đáp án của bạn được chấp nhận nếu ~\frac{|a - b|}{\max(1, b)} \leq 10^{-6}~.

Scoring

• Subtask ~1~ (~15\%~ số điểm): ~n \le 10^3~, ~|x_i|, |y_i| \leq 5 \times 10^4~ và bánh luôn có dạng đa giác lồi.
• Subtask ~2~ (~15\%~ số điểm): ~n \le 10^3~, ~|x_i|, |y_i| \leq 5 \times 10^4~ và các cạnh của bánh luôn song song với trục tọa độ.
• Subtask ~3~ (~20\%~ số điểm): ~n \le 10^3~, ~|x_i|, |y_i| \leq 5 \times 10^4~.
• Subtask ~4~ (~15\%~ số điểm): Bánh luôn có dạng đa giác lồi.
• Subtask ~5~ (~15\%~ số điểm): Các cạnh của bánh luôn song song với trục tọa độ.
• Subtask ~6~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

8 3
3 3
3 0
-2 0
-2 1
0 1
0 3
-2 3
0 6
-2 3
0 3
-3 0

Sample Output 1

18.5
13.5
 5.0

Để mở đầu cho kỉ nguyên chinh phục vũ trụ, các nhà khoa học ở hành tinh Alpha đang tiến hành thiết kế một chiếc tàu vũ trụ. Trong đó, bộ phận quan trọng nhất là hệ thống động cơ của tàu.

Các nhà khoa học đã mô hình hóa vũ trụ thành hệ trục tọa độ Oxy trong không gian hai chiều, lấy hành tinh Alpha làm gốc tọa độ. Có ~n~ vị trí có thể lắp ráp động cơ trên tàu vũ trụ. Việc lắp ráp động cơ ở vị trí thứ ~i~ tốn chi phí là ~w_i~, và sẽ cho phép tàu di chuyển theo hướng ~(a_i, b_i)~. Cụ thể, giả sử tàu đang nằm ở tọa độ ~(x, y)~ thì khi sử dụng động cơ thứ ~i~ trong khoảng thời gian ~t~ (~t~ là số thực không âm, có thể lớn tùy ý) tàu sẽ đi đến vị trí ~(x + a_i × t, y + bi × t)~.

Một trong những tiêu chí quan trọng nhất trong thiết kế hệ thống tên lửa là tàu phải đi đến được mọi địa điểm trong vũ trụ, tức là với mọi điểm ~(x, y)~, tàu luôn có thể xuất phát từ gốc tọa độ và đi đến điểm ~(x, y)~ chỉ bằng các động cơ được lắp ráp. Nói cách khác, giả sử tàu được lắp ráp động cơ ở các vị trí ~r_1, r_2, . . . , r_k~ thì cần đảm bảo rằng, với mọi điểm ~(x, y)~ luôn tồn tại một bộ số thực ~t_1, t_2, . . . , t_k~ không âm sao cho ~a_{r_1} × t_1 + a_{r_2} × t_2 + . . . + a_{r_k} × t_k = x~ và ~b_{r_1} × t_1 + b_{r_2} × t_2 + . . . + b_{r_k} × t_k = y~.

Yêu cầu: Hãy giúp các nhà khoa học hành tinh Alpha chọn ra các vị trí cần lắp ráp động cơ sao cho tàu có thể đi đến được mọi điểm trong vũ trụ, và tổng chi phí lắp ráp động cơ là nhỏ nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~n (1 ≤ n ≤ 2 × 10^5)~ cho biết số vị trí có thể lắp động cơ. • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, w_i (|a_i|, |b_i|≤ 10^9, 1 ≤ w_i ≤ 10^9)~ cho biết hướng và chi phí lắp ráp động cơ ở vị trí thứ ~i~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất để lắp ráp động cơ sao cho tàu có thể đi đến mọi điểm. Trong trường hợp không tồn tại các lắp ráp động cơ thỏa yêu cầu đề bài, hãy ghi ra ~-1~.

Sample Input 1

7
0 3 2
0 3 3
1 -1 3
-2 4 2
-4 0 1
2 1 2
0 0 1

Sample Output 1

6

Sample Input 1

2
1 0 10
0 1 10

Sample Output 1

-1

Giải thích

• Trong ví dụ thứ nhất, ta sẽ lắp động cơ ở các vị trí ~1, 3, 5~ với tổng chi phí là ~2 + 3 + 1 = 6~. Cách lắp động cơ này sẽ cho phép tàu vũ trụ đi đến mọi điểm khi xuất phát từ điểm ~(0, 0)~. Ví dụ, để đi đến điểm ~(1, -3)~, ta có thể dùng động cơ ở vị trí ~3~ trong khoảng thời gian ~3~ để đi đến điểm ~(3, -3)~, rồi dùng động cơ ở vị trí ~5~ trong khoảng thời gian ~0.5~ để đi đến điểm ~(1, -3)~. • Trong ví dụ thứ hai, ta nhận thấy rằng, dù lắp cả hai động cơ thì vẫn tồn tại điểm mà tàu không thể đi đến được, ví dụ như điểm ~(-1, -2)~.

Constraints

• Có 30% số test ứng với ~n ≤ 16~. • Có 20% số test khác ứng với ~n ≤ 50~. • Có 30% số test khác ứng với ~n ≤ 2000~. • 20% số test còn lại không có ràng buộc gì thêm.