Cho dãy số nguyên dương ~a[1], a[2], …, a[N]~. Xét cách chia dãy số ~a~ thành ~K~ nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của ~a~. Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số ~a~ thành ~K~ nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương ~N~ và ~K~ (~K \le N~)
• Dòng 2: Gồm ~N~ số nguyên dương ~a[1], a[2], …, a[N]~

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

5 1
1 2 3 4 5   

Output 1

5

Input 2

5 2
1 2 3 4 5   

Output 2

6

Giới hạn:

• 14% số điểm: ~1\le N\le100, K\le min(N, 5)~
• 18% số điểm: ~1\le N\le20~
• 21% số điểm: ~1\le N\le100~
• 47% số điểm: ~1\le N\le100000, K\le min(N, 100).~

Một dãy các số ~a_1,a_2,...,a_n~ được gọi là dãy kẹp nếu ~a_1 \le a_i \le a_n~, ~\forall i \in [1,n]~. Nếu ~n \le 2~ thì là dãy kẹp nếu ~a_1 \le a_n~.

Các ví dụ về dãy kẹp: ~[1],[1,1],[3,4,3,4],[1,3,2,4]~. Các ví dụ về dãy không phải dãy kẹp: ~[],[2,3,1],[2,1,4,3]~.

Cho mảng ~a = [a_1,a_2,...,a_n]~, hãy đếm xem có bao nhiêu mảng con liên tiếp của ~a~ là dãy kẹp.

Input

• Dòng đầu chứa số nguyên dương ~𝑛~ ~(𝑛 ≤ 10^6)~.
• Dòng sau chứa dãy ~a~ ~(1 \le a_i \le 10^9)~.

Subtask

• Subtask ~1~ ~(10\%)~ : ~n \le 300~
• Subtask ~2~ ~(20\%)~ : ~1 \le n \le 10^5, 1 \le a_i \le 2~
• Subtask ~3~ ~(20\%)~ : ~n \le 5000~
• Subtask ~4~ ~(30\%)~ : ~n \le 10^5~
• Subtask ~5~ ~(20\%)~: Không giới hạn gì thêm

Output

• In ra một số là kết quả bài toán.

Sample Input 1

5
1 2 4 3 5

Sample Output 1

11

Sample Input 1

8
2 1 6 3 6 7 8 5

Sample Output 1

18

Messi đang muốn đi tập Gym để chụp hình đăng Instagram. Phòng Gym của anh có ~n~ quả tạ được đánh số từ ~1~ tới ~n~. Quả tạ thứ ~i~ có trọng lượng ~w_i~.

Vì là GOAT, Messi có thể nâng nhiều tạ một lúc, tuy nhiên, các tạ mà anh ấy chọn sẽ phải tuân thủ điều kiện sau:

• Đối với mọi chữ số từ ~0~ tới ~9~, số lần chữ số đó xuất hiện trong các tạ được chọn không vượt quá ~2~.

Ví dụ, Messi có thể nâng các tạ ~[10,8,1]~ nhưng không thể nâng tạ ~[700,70]~ vì số ~0~ lặp lại ~3~ lần.

Vì muốn có một cơ bắp nhìn quá là ưng, hãy in ra trọng lượng tối đa của các tạ mà Messi có thể mang.

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ ~(1\le n \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~w~ ~(1 \le w_i \le 10^9)~.

Output:

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

Sample Input 1

4
99 9 58 72

Sample Output 1

229

Sample Input 2

1
777

Sample Output 2

0

Đối với Mirko, không có hạnh phúc nào lớn hơn việc tìm thấy một cuộn băng dính mới, và ngày hôm nay anh ấy đặc biệt hạnh phúc vì anh ấy còn tìm thêm được cuốn lịch Advent của Slavko.

Cuốn lịch Advent có thể biểu diễn như một bảng hình chữ nhật với ~n~ hàng và ~m~ cột, mỗi ô vuông chứa một cửa sổ nhỏ, và đằng sau mỗi cửa sổ là một miếng sô cô la. Slavko đã mở một số ô trong số đó, còn những cửa sổ khác vẫn đang đóng.

Mirko quyết định sử dụng cuộn băng dính của anh ấy để dán lại tất cả những cửa sổ đóng. Cuộn băng dính thì dài vô tận, và nó có chiều rộng bằng ~1~ ô của cuốn lịch. Mirko có thể xé một đoạn băng dính và dùng nó để dán một đoạn liền kề những ô cửa sổ đã đóng theo chiều dọc hoặc chiều ngang. Anh ấy không muốn dán nhiều hơn một lớp băng dính lên bất kỳ cửa sổ nào, vì anh ấy vẫn muốn giữ tình bạn với Slavko.

Anh ấy đang tự hỏi rằng, anh ấy cần tối thiểu bao nhiêu mẩu băng dính để dán lại hết các cửa sổ đóng trong cuốn lịch.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 1000~, ~1 \le m \le 10~), là kích thước của cuốn lịch Advent.

• Mỗi trong ~n~ dòng tiếp theo chứa ~m~ ký tự . và #, biểu diễn cuốn lịch Advent.

• Ký tự . mô tả một ô cửa sổ đã mở

• Ký tự # mô tả một ô cửa sổ đang đóng

Output

In ra số lượng nhỏ nhất các mẩu băng dính cần thiết để dán hết những ô cửa sổ đóng.

Sample Input 1

2 3
#.#
###

Sample Output 1

3

Sample Input 2

4 3
.#.
###
.##
.#.

Sample Output 2

3

Giải thích ví dụ 1

Một cách dán hợp lý là:

• Dán một đoạn cho cột đầu tiên,

• Một đoạn cho cột thứ 3,

• Và một đoạn cho ô ở hàng 2, cột 2.

• Tổng cộng cần 3 đoạn băng dính.

Cho ma trận vuông ~n \times n~, các hàng được đánh số từ ~1~ tới ~n~, các cột được đánh số từ ~1~ tới ~n~. Các ô được sắp xếp theo thứ tự từ trái sang phải, từ trên xuống dưới, ô ~(i,j)~ có giá trị là ~a_{i,j}~.

Ivan Tèo đang đứng ở ô ~(1,1)~ của ma trận, trong mỗi lần đi, cậu chỉ có thể đi sang phải hoặc xuống dưới, nói cách khác, nếu đang ở ô ~(i,j)~, cậu chỉ có thể đi sang ô ~(i+1,j)~ hoặc ~(i,j+1)~. Gọi ~Best(i,j)~ là giá trị lớn nhất có thể nếu Ivan Tèo đi từ ô ~(1,1)~ tới ô ~(i,j)~. Vì cảm thấy rằng nếu chỉ hỏi các ~Best(i,j)~ thì quả là nhàm chán và không đánh giá đúng được tiềm năng của Tèo, ~mrhee~ quyết định tạo ra một giá trị mới như sau:

• Gọi ~S~ là tổng các ~Best(i,j)~ của mọi ô ~(i,j)~ trên ma trận.
• Nói cách khác, ~S = \sum Best(i,j)~, với mọi ~(1 \le i,j \le n)~.

Vì lại cảm thấy việc in ra ~S~ của ma trận hiện tại là quá dễ với Tèo, ~mrhee~ quyết định tạo ra ~q~ sự thay đổi, sự thay đổi thứ ~i~ có dạng như sau:

• Cho ba số nguyên ~u_i,v_i,delta_i~ ~(1 \le u_i,v_i \le n, -1\le delta_i \le 1)~, tức gán giá trị ~a_{u_i,v_i} = a_{u_i,v_i} + delta_i~.
• Sau mỗi truy vấn, hãy in ra giá trị ~S~ của ma trận mới.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(1 \le n \le 1000, 1 \le q \le 3 \times 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm ~n~ số nguyên, số thứ ~j~ miêu tả giá trị ~a_{i,j}~ ~(-10^2 \le a_{i,j} \le 10^2)~ của ma trận.
• ~q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i,v_i,delta_i~ ~(1 \le u_i,v_i \le n, -1 \le delta_i \le 1)~ miêu tả truy vấn thứ ~i~.

Output:

• Gồm một dòng in ra số cặp ~(i,j)~ thỏa mãn.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~q \le 10~.
• Subtask ~2~ (~25\%~ số điểm): Ô ~(u_i,v_i)~ trong mọi truy vấn là giống nhau và ~q \le 3000~, đồng thời ~delta_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~30\%~ số điểm): ~q \le 3000~
• Subtask ~4~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2 2
1 2
2 2
1 2 0
2 1 1

Sample Output 1

12
14

Sample Input 2

4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
1 1 1
2 2 -1
3 1 1
1 3 -1

Sample Output 2

196
195
203
199

Explanation

Ở ví dụ ~1~, sau truy vấn đầu, bảng không thay đổi gì, ta có các ~Best(i,j)~ như sau:

• ~Best(1,1) = 1~
• ~Best(1,2) = 3~
• ~Best(2,1) = 3~
• ~Best(2,2) = 5~

Sau khi tăng ô ~(2,1)~ lên ~4~ đơn vị, ta có:

• ~Best(1,1) = 1~
• ~Best(1,2) = 3~
• ~Best(2,1) = 4~
• ~Best(2,2) = 6~

Cho dãy số nguyên dương ~𝐴~ có ~𝑁~ phần tử ~𝑎_1, 𝑎_2, … , 𝑎_N~. Có ~𝑄~ truy vấn có dạng ~𝐿, 𝑅, 𝐾~ với ý nghĩa như sau:

• Xét dãy con ~𝐵~ là dãy con của ~𝐴~ gồm các phần tử liên tiếp từ vị trí ~𝐿~ đến vị trí ~𝑅~ : ~𝑎_L, 𝑎_{L+1}, … , a_R~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~, ta xây dựng dãy số ~𝐶~ bằng cách coi ~𝐶~ là tập hợp tất cả các dãy con liên tiếp của ~B~. Ví dụ: dãy ~𝐵 = \{1, 2, 1\}~ các dãy con của ~B~ là ~\{1\}, \{2\}, \{1\}, \{1,2\}, \{2,1\}, \{1,2,1\}~ ta sẽ có dãy ~𝐶 = \{1, 2, 1, 1, 2, 2,1, 1,~~ 2, 1\};~
• Sắp xếp dãy ~𝐶~ theo thứ tự không giảm và đưa ra phần tử thứ ~𝐾~. Ví dụ: với dãy ~𝐶~ trên ta sắp xếp thành ~\{1, 1, 1, 1, 1, 1, 2, 2, 2, 2\}~ và phần tử thứ ~8~ là ~2~.

Yêu cầu: Cho dãy số ~𝐴~ và ~𝑄~ truy vấn như trên, hãy đưa ra kết quả phần tử thứ ~𝐾~ của dãy số ~𝐶~ tương ứng trong mỗi truy vấn.

Dữ liệu nhập vào từ file văn bản DLT.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~𝑁~ và ~𝑄~ ~(1 ≤ 𝑁, 𝑄 ≤ 5 \times 10^5)~ là số phần tử của dãy số ~𝐴~ và số lượng truy vấn~;~
• Dòng thứ hai gồm ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_N~ ~(1 ≤ 𝑎_i ≤ 5 \times 10^5; \ 1 ≤ 𝑖 ≤ 𝑁);~
• ~𝑄~ dòng sau, mỗi dòng chứa ba số ~𝐿, 𝑅, 𝐾~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~ mô tả truy vấn.

Dữ liệu đảm bảo đúng đắn, luôn có kết quả.

Kết quả ghi ra file văn bản DLT.OUT:

~𝑄~ dòng là kết quả tương ứng của mỗi truy vấn.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 100;~
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thoả mãn: ~𝑁, 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 5000;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 10^5; 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
1 2 1 3 2
1 3 8
1 4 18

Output

2
3

Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

• Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.
• Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ của bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Constraint

• ~1 \le n \le 400~.
• ~-10^6 \le b_i, a_i \le 10^6~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a~.
• Dòng thứ ba gồm ~n~ số nguyên miêu tả dãy ~b~.

Output

• In ra ~S~ lớn nhất tìm được.

Subtask

• ~30\%~ số test có ~n \le 10~
• ~40\%~ số test có ~n \le 50~.
• ~30\%~ số test có ~n \le 400~.

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Explanation 1

• Chọn đoạn ~[1,5]~ và ~[2,5]~.

Cho dãy số độ dài ~n~ và một số nguyên ~k~. Mỗi vị trí ~i~ có hai thuộc tính:

• ~t_i \in [1..k]~ là loại trái tại vị trí ~i~,
• ~a_i~ là số lượng trái thu được tại vị trí ~i~.

Bạn được phép chọn một đoạn liên tục ~[l..r]~ (với ~1 \le l \le r \le n~) và hái tất cả trái trên đoạn đó. Gọi ~ x_j \;=\; \sum_{\substack{i=l}}^{r} \bigl[a_i \,\text{nếu}\, t_i = j\bigr] \quad\text{với } j=1,2,\dots,k ~ là tổng số trái loại ~j~ thu được trong đoạn ~[l..r]~. Mỗi chiếc bánh cần đúng một trái mỗi loại, nên số bánh có thể làm được là ~ \min(x_1, x_2, \dots, x_k). ~ Phần trái dư thừa Chow sẽ được ăn, tính bằng ~ \bigl(x_1 + x_2 + \cdots + x_k\bigr)\;-\;k\times\min(x_1, x_2, \dots, x_k). ~

Hãy tìm giá trị lớn nhất của biểu thức trên khi bạn chọn đoạn ~[l..r]~ sao cho Chow được ăn nhiều trái nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le n, k \le 3\cdot10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~t_1, t_2, \dots, t_n~ ~(1 \le t_i \le k)~.
• Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

In ra một số nguyên - giá trị lớn nhất của ~ \sum_{j=1}^{k} x_j \;-\; k \,\min_{1 \le j \le k} x_j ~ khi chọn đoạn ~[l..r]~.

Sample Input 1

4 3
2 1 2 3
6 3 3 4

Sample Output 1

12

Cho lưới ô vuông rộng vô tận, tâm của lưới ô vuông có tọa độ (0, 0). Có ~n~ ngôi nhà được xây dựng trên lưới ô vuông. Trong 1 đơn vị thời gian, người ~A~ có thể di chuyển đến các ô liền kề của lưới (8 ô liền kề). Khoảng cách giữa 2 ngôi nhà là thời gian ngắn nhất di chuyển từ nhà này đến nhà kia. Trong lúc nhàn rỗi, bạn Lương tính toán hết tất cả khoảng cách giữa 2 ngôi nhà và sắp xếp chúng thành dãy không giảm. Hãy tìm số thứ ~k~ trong dãy.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, k~ ~(2 \leq n \leq 10^5, k \leq \frac{n (n - 1)}{2})~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~x, y~ là tọa độ của nhà thứ ~i~ ~(|x|, |y| \leq 10^9)~.

Output

• In ra số nguyên là kết quả bài toán.

Scoring

• Subtask 1: ~\ n \leq 2000~
• Subtask 2: ~\ y_i = 0~ với mọi ~i~
• Subtask 3: ~\ k = 1~
• Subtask 4: không có dữ kiện gì thêm

Sample Input 1

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

Sample Output 1

4

Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:

Input:

• Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
• ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.

Constraints

• ~1 \leq n \leq 5 \times 10^5~
• ~0 \leq m \leq 5 \times 10^5~

Subtask

• ~10\%~ số test có ~1 \le n \le 4~.
• ~30\%~ số test khác có ~1 \le n \le 60~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Output:

• In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.

Sample Input 1:

4 2
1 2
4 3

Sample Output 1:

2

Sample Input 2:

3 3
1 1
2 2
3 3

Sample Output 2:

-1

Explanation

• Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.

• Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.

Nhân dịp sinh nhật Alice được cha mẹ tặng ~n~ bộ xếp chữ, được đánh số từ ~1~ đến ~n~. Bộ xếp chữ thứ ~i~ có ~a_i~ chữ cái "A" và ~b_i~ chữ cái "B". Alice đưa ra một trò chơi như sau: chọn ra hai bộ xếp chữ trong ~n~ bộ, nhóm các chữ cái "A" và chữ cái "B" của hai bộ đã chọn, rồi xếp tất cả chúng thành một hàng ngang. Ví dụ là có ~3~ chữ cái "A" và ~4~ chữ cái "B" thì "ABABABB" và "BBBBAAA" là một trong các cách xếp hợp lệ, và "AAAABBB" là một trong các cách xếp không hợp lệ.

Alice muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9+7~.

Input

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

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~, ~b_i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9+7~.

Scoring

• Subtask 1 (~20~ điểm): ~n \le 5~; ~a_i, b_i \le 10~.
• Subtask 2 (~20~ điểm): ~n \le 2000~.
• Subtask 3 (~30~ điểm): ~a_i, b_i \le 50~.
• Subtask 4 (~30~ điểm): Không có ràng buộc gì thêm.

Example

Input

2
1 1
2 1

Output

10

Vương quốc có ~n~ thành phố và ~n-1~ con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý ~y~ nếu ~x~ nằm trên đường đi đơn từ ~y~ đến 1. Sản lượng lương thực tại thành phố ~x~ là ~w_x~. Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại ~u~ là ~∑_{v=1}^n {w_v×d(v,u)}~ với ~d(v,u)~ là số cạnh trên đường đi đơn từ ~v~ đến ~u~.

Có ~Q~ thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng ~1\ u\ c~ hoặc ~2\ u\ c~ tương ứng là tăng ~w_u~ lên ~c~ đơn vị hoặc tăng ~w_v~ lên ~c~ đơn vị với mọi ~v~ quản lý bởi ~u~. Sau mỗi thay đổi, cần tìm đỉnh ~u~ để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều ~u~ như vậy thì chọn ~u~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
• Dòng thứ hai chứa ~n~ số ~w_1,w_2,...,w_n~;
• Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số ~u\ v~ mô tả một cạnh của cây;
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa ba số ~t\ u\ c~ mô tả một thay đổi

Output

• Ghi ~Q~ dòng là chỉ số của đỉnh được chọn sau thay đổi thứ ~Q~.

Scoring

• Trong tất cả các test: ~n,Q ≤ 10^5; 1 ≤ w_i ≤ 10^6; |c| ≤ 10^6.~
• Có 12% số test với ~n,Q ≤ 5000~;
• Có 16% số test có cạnh nối từ ~x~ đến ~x - 1~ với mọi ~2 ≤ x ≤ n;~
• Có 16% số test có cạnh nối từ ~x~ đến ~[x/2]~ với mọi ~2 ≤ x ≤ n;~
• Có 20% số test không có thay đổi loại 2;
• Có 36% số test với ràng buộc gốc. uộc gốc

Sample Input 1

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

Sample Output 1

2 
2 
1

Cho ~3~ điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem ~3~ điểm này có tạo thành hình tam giác được hay không?

Input

• ~3~ điểm có tọa độ nguyên.

Output

• In ra ~0~ nếu ~3~ điểm đã cho không thể tạo được một tam giác, ngược lại in ra ~1~.

Constraints

• Tọa độ của ~3~ điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Sample Input 1

0 0 0 1 1 0

Sample Output 1

1

Sample Input 2

727 1 727 2 727 3

Sample Output 2

0

Cho một đa giác lồi ~n~ đỉnh, các đỉnh được nhập theo thứ tự ngược chiều kim đồng hồ.

Hãy tính diện tích của đa giác lồi đã cho.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~ trên đa giác.

Output

• In ra kết quả của bài toán lấy đến số thập phân thứ nhất.

Constraints

• ~1 \le n \le 10^2~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

4
6 1
7 4
2 5
1 1 

Sample Output 1

18.0

Trên hệ tọa độ ~Oxy~, cho một đa giác lồi gồm ~n~ đỉnh. Có ~m~ truy vấn, mỗi truy vấn gồm một điểm, hãy kiểm tra xem điểm đó có nằm trong đa giác đã cho hay không.

https://www.youtube.com/watch?v=aoxOPx2BIHE

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~ trên đa giác. Các đỉnh được nhập vào theo thứ tự ngược chiều kim đồng hồ.
• Dòng tiếp theo gồm số nguyên dương ~m~.
• ~m~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thuộc truy vấn ~i~.

Output

• Gồm ~m~ dòng, dòng ~i~ in ra ~0~ nếu điểm thứ ~i~ không nằm trong đa giác, ngược lại in ra ~1~.

Constraints

• ~1 \le n,m \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

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

Sample Output 1

0
0
1
1

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đường thẳng, đường thẳng thứ ~i~ đi qua ~2~ điểm ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách từ điểm ~P~ tới một trong các đường thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ mà đường thẳng ~i~ đi qua.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

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

Sample Output 1

2.77

Sample Input 2

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

Sample Output 2

2.24

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đoạn thẳng, đoạn thẳng thứ ~i~ có ~2~ đầu mút là ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách ngắn nhất từ điểm ~P~ tới một trong các đoạn thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ là đầu mút của đoạn thẳng ~i~.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

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

Sample Output 1

4.12

Sample Input 2

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

Sample Output 2

3.16

Cho ~n~ điểm trên mặt phẳng ~Oxy~. Hãy đếm số bộ ba điểm thẳng hàng.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Output

• In ra số bộ ba điểm thẳng hàng.

Constraints .

• ~1 \le n \le 2000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^4,10^4]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 200~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

6
0 0
0 1
0 2
1 1
2 0
2 2

Sample Output 1

3

Cho ~n~ điểm trên mặt phẳng ~Oxy~ và tham số ~p~.

Hãy xác định xem, có tồn tại một đường thẳng sao cho có ít nhất ~p~ phần trăm các điểm trong ~n~ điểm được cho nằm chính xác trên đường thẳng đó hay không.

Input

• Dòng đầu gồm số nguyên dương ~t~ miêu tả số bộ test.
• Mỗi bộ test bao gồm:
  • Dòng đầu gồm số nguyên dương ~n~.
  • Dòng thứ hai gồm số nguyên dương ~p~.
  • ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Đảm bảo rằng không có hai điểm nào trùng khớp.

Output

• Với mỗi bộ test, nếu tồn tại đường thẳng thỏa mãn thì in ra "possible", ngược lại in ra "impossible".

Constraints .

• ~1 \le t \le 5~.
• ~1 \le n \le 10^5~.
• ~35 \le p \le 100~
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

2
5
55
0 0
10 10
10 0
0 10
3 3
5
45
0 0
10 10
10 0
0 10
3 4

Sample Output 1

possible
impossible

Explanation 1

Ở ví dụ ~1~, tồn tại đường thẳng đi qua (ít nhất) ~3~ điểm trong số ~5~ điểm trên.

Ở ví dụ ~2~, không tồn tại đường thẳng nào đi qua nhiều hơn hoặc bằng ~45\%~ số điể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 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 ~n~ điểm trên hệ trục tọa độ ~OXY~. Điểm thứ ~i~ gọi là ~P_i~.

Hai tam giác ~ABC~ và ~CDE~ được định nghĩa là bằng nhau nếu:

• ~AB = CD~
• ~BC = DE~
• ~AC = CE~
• ~\angle {BAC} = \angle {DCE}~
• ~\angle {ABC} = \angle {CDE}~
• ~\angle {ACB} = \angle {CED}~

Bạn cần đếm số bộ sáu số nguyên dương ~(i_1,i_2,i_3,j_1,j_2,j_3)~ sao cho chúng khác nhau đôi một và:

• ~1 \le i_1,i_2,i_3,j_1,j_2,j_3 \le n~
• ~i_1 < i_2 < i_3~
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}}~ không suy biến, nói cách khác nó có diện tích dương.
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}} = \triangle {P_{j_1}P_{j_2}P_{j_3}}~

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~.

Constraints

• ~n \le 100~
• ~1 \le x_i , y_i \le 10^9~

Subtask

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

Output

• In ra số bộ sáu tìm được.

Sample Input 1:

6
2 2
4 6
6 2
14 8
10 6
14 4

Sample Output 1:

4

Explanation 1:

Ta có ~4~ bộ như sau:

• ~(1,2,3,4,5,6)~
• ~(1,2,3,4,6,5)~
• ~(4,5,6,1,2,3)~
• ~(4,5,6,1,3,2)~

Trên mặt phẳng tọa độ, cho ~n~ điểm có tọa độ nguyên. Hãy tính chu vi của bao lồi của tập điểm này.

https://pastebin.com/rSX6jR0H

Input

• Dòng đầu gồm số nguyên dương ~n~ là số điểm.
• ~n~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra chu vi của bao lồi của tập điểm, kết quả lấy chính xác tới ~1~ chữ số thập phân.

Constraints

• ~3 \le n \le 10^4~.
• ~-10^4 \le x_i,y_i \le 10^4~.

Sample Input 1

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

Sample Output 1

12.2

Explanation 1

Bao lồi cần tìm gồm ~3~ điểm ~(1,1),(2,5),(5,3)~, có chu vi là ~12.200792856~.

Cho ~n~ điểm trên trục tọa độ ~Oxy~, hãy tìm bao lồi gồm nhiều đỉnh nhất của tập điểm đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số điểm.

• ~n~ dòng sau, mỗi dòng chứa ~2~ số ~x_i,y_i~ miêu tả tọa độ điểm thứ ~i~.

  Output

• In ra số đỉnh của bao lồi cần tìm.

Constraints

• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

5
2 1
2 3
2 5
6 3
4 3

Sample Output 1

4

Explanation 1

Các đỉnh ~A,B,C,D~ nằm trong bao lồi cần tìm.

~3~ đỉnh ~A,C,D~ cũng tạo ra một bao lồi, tuy nhiên số đỉnh của nó không phải là tối đa.

Ở một nông trại nọ, có ~n~ cái cọc. Để bảo vệ con cừu của mình, bác nông dần cần dựng lên các rào chắn, sau đó đặt nó vào vị trí được bao bởi nhiều rào chắn nhất. Mỗi rào là một đa giác không tự cắt được tạo ra bằng cách nối các cái cọc lại với nhau bằng dây thừng, mỗi cái cọc thuộc không quá ~1~ rào chắn. Các rào phải được tạo ra sao cho với mỗi cặp rào chắn bất kì ~X~ và ~Y~ thì diện tích chung của ~X~ và ~Y~ là ~min (S(X), S(Y))~ hoặc ~0~.

Trên mặt phẳng tọa độ, các cái cọc được coi như các điểm với tọa độ nguyên. Hãy xác định xem con cừu sẽ được bảo vệ bởi tối đa bao nhiêu rào chắn.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các cọc.

Output

• In ra số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n \le 2000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^4,10^4]~.

Sample Input 1

12
-9 -5
8 -4
-6 -4
0 -8
-4 -2
-3 -9
7 6
-2 9
-3 8
9 6
4 1
0 -7

Sample Output 1

2

Cho ~n~ điểm trên mặt phẳng tọa độ, hãy tìm ~3~ điểm sao cho chúng tạo thành một tam giác không suy biến và diện tích của nó là lớn nhất có thể.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng điểm.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x_i,y_i~ ~(-10^7 \le x_i,y_i \le 10^7)~. Với ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra số nguyên duy nhất là diện tích tam giác lớn nhất được tạo thành từ ~3~ điểm trong các điểm đã cho. Kết quả lấy chính xác tới chữ số thập phân thứ nhất.

Constraints

• ~3 \le n \le 3000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^7,10^7]~.

Subtask

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

Sample Input 1

5
3 6
2 7
1 8
4 9
1 4

Sample Output 1

6.0

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 độ vuông góc ~Oxy~, cho tọa độ ~N~ điểm trong đó không có ba điểm nào thẳng hàng.

Yêu cầu: Tìm hai điểm trong ~N~ điểm để đường thẳng chứa hai điểm đó chia ~N-2~ điểm còn lại thành hai phần sao cho tổng số điểm của mỗi phần chênh lệnh nhau không quá ~1~.

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

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 10^5)~ là số lượng điểm;
• ~N~ dòng sau, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của một điểm ~(|x| ≤ 10^9~; ~\ |y| ≤ 10^9)~.

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

Một dòng gồm bốn số nguyên là toạ độ của hai điểm thoả mãn. Có thể có nhiều kết quả, ghi ra một kết quả bất kì.

Ràng buộc

• Có ~30\%~ số test ứng với ~N ≤ 100~;
• ~30\%~ số test khác ứng với ~N ≤ 5000~;
• ~40\%~ số test còn lại ứng với ~N ≤ 10^5~.

Ví dụ

Input

4
0 0
0 1
1 1
1 0

Output

0 0 1 1

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.

Các bé học sinh trường mầm non SuperKids tỏ ra say mê với các trò chơi đòi hỏi tư duy thuật toán chuyên nghiệp.

Nhân dịp đến thăm trường, giáo sư X bày ra một trò chơi cho các bạn nhỏ tại đây.

Ban đầu, người chơi được cho 𝑛 thùng nước đánh số từ ~1~ tới ~n~. Thùng thứ ~i~ có ~a_i~ lít nước. Người chơi được quyền múc một lượng nước bất kỳ từ một thùng chuyển sang thùng liền sau (chuyển từ thùng ~i~ sang thùng ~i + 1~ với ~i~ tùy chọn thỏa mãn ~1 \le i < n~). Năng lượng tiêu tốn cho thao tác này đúng bằng lượng nước được chuyển (có thể không phải là số nguyên)

Nhiệm vụ của người chơi là phải làm cho lượng nước trong các thùng sắp xếp thứ tự không giảm, tức là:

• ~a_1 \le a_2 \le ... \le a_n~

Yêu cầu: Hãy tìm phương án chơi sao cho tổng năng lượng tiêu tốn là ít nhất

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra một số thực duy nhất với ~1~ chữ số sau dấu chấm thập phân là tổng năng lượng tiêu tốn nếu các bé chơi theo phương án của bạn.

Constraints .

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 10^6~

Sample Input 1

6
1 3 0 0 3 0

Sample Output 1

4.5

Explanation 1

Ta sẽ chuyển nước để được lượng nước trong các thùng là ~1.0,1.0,1.0,1.0,1.5,1.5~

Chuyển ~2~ lít từ thùng ~2~ sang thùng ~3~

Chuyển ~1~ lít từ thùng ~3~ sang thùng ~4~

Chuyển ~1.5~ lít từ thùng ~5~ sang thùng ~6~