Vừa mới lĩnh lương, Alob và Bice quyết định dành ra số tiền ~n~ đồng đi shopping hâm nóng tình cảm. Alob muốn dành toàn bộ số tiền của mình để mua búp bê, còn Bice sẽ dành toàn bộ số tiền của mình để mua lego.

Trong siêu thị có vô số loại lego và búp bê, loại lego thứ ~i~ có giá là ~i~ đồng và loại búp bê thứ ~i~ cũng có giá là ~i~ đồng. Hai bạn sẽ chia nhau ~n~ đồng tiền theo ý thích và đi mua sắm, mỗi người chỉ mua một loại đồ chơi duy nhất (có thể mua nhiều món đồ cùng loại) đến khi hết tiền sao cho số tiền mang đi không thừa không thiếu và mỗi bạn mua được ít nhất một món đồ chơi.

Chẳng hạn, nếu ~n=8~, một cách mua có thể là: Alob và Bice mỗi người được chia ~4~ đồng; Alob mua ~2~ con búp bê giá ~2~ đồng, còn Bice mua ~1~ lego giá ~4~ đồng. (Lưu ý Alob không thể mua ~1~ con búp bê giá ~3~ đồng (do không sử dụng hết tiền) hoặc một con ~3~ đồng một con ~1~ đồng (do chỉ được mua ~1~ loại đồ chơi)).

Hãy tính xem Alob và Bice có tổng bao nhiêu cách mua đồ.

Input

Một số nguyên duy nhất là số nguyên dương ~n~ là số tiền mà Alob và Bice có (~1 \leq n \leq 10^6~).

Output

Một số nguyên duy nhất là số cách mua đồ có thể của Alob và Bice.

Scoring

• Subtask ~1~ (~40~ điểm): ~n \leq 500~.

• Subtask ~2~ (~60~ điểm): Không có điều kiện gì thêm.

Sample Input 1

2

Sample Output 1

1

Sample Input 2

4

Sample Output 2

8

Notes

Trong test thứ nhất, chỉ có duy nhất ~1~ cách mua sắm là: Alob dùng ~1~ đồng mua búp bê giá ~1~ đồng, Bice dùng ~1~ đồng mua lego giá ~1~ đồng.

Trong test thứ hai, có tổng cộng ~8~ cách chia thỏa mãn là:

• Alob mua ~1~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~3~ đồng.

• Alob mua ~1~ búp bê giá ~1~ đồng, Bice mua ~3~ lego giá ~1~ đồng.

• Alob mua ~1~ búp bê giá ~2~ đồng, Bice mua ~1~ lego giá ~2~ đồng.

• Alob mua ~1~ búp bê giá ~2~ đồng, Bice mua ~2~ lego giá ~1~ đồng.

• Alob mua ~2~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~2~ đồng.

• Alob mua ~2~ búp bê giá ~1~ đồng, Bice mua ~2~ lego giá ~1~ đồng.

• Alob mua ~3~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~1~ đồng.

• Alob mua ~1~ búp bê giá ~3~ đồng, Bice mua ~1~ lego giá ~1~ đồng.

Cho dãy số nguyên ~a~ độ dài ~n~, bạn phải lần lượt thực hiện thao tác đúng ~2~ lần, mỗi thao tác bao gồm ~2~ bước sau:

• Chọn ~2~ giá trị ~l~, ~r~ sao cho ~1 \leq l \leq r \leq n~.

• Đổi dấu các phần tử trong đoạn từ ~l~ đến ~r~ của dãy ~a~. Nói cách khác, gán ~a[i] = -a[i]~ với mọi ~l \leq i \leq r~.

Hãy tìm cách thực hiện đúng ~2~ thao tác sao cho sau khi thực hiện, tổng các phần tử dãy ~a~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên ~n~ là độ dài của dãy ~a~ (~n \leq 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3,..., a_n~ là các phần tử của dãy ~a~ (~-10^9 \leq a_i \leq 10^9~)

Output

Một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (~20~ điểm): ~n \leq 100~.

• Subtask 2 (~30~ điểm): ~n \leq 1000~.

• Subtask 3 (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4
-1 2 -3 -4

Sample Output 1

10

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một hoán vị ~p~ độ dài ~n~.

Ta thực hiện một trò chơi gồm ~n~ bước như sau: ở bước thứ ~i~, ta xóa đi phần tử ~p_i~.

Yêu cầu: Trước khi thực hiện mỗi bước, hãy in ra tổng lớn nhất của đoạn con gồm các phần tử liên tiếp, có độ dài lớn hơn ~0~ và chưa có phần tử nào bị xóa trên dãy ~a~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ miêu tả độ dài dãy ~a~ và hoán vị ~p~ ~(1 \le n \le 5*10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a_1,a_2,...,a_n~ ~( |a_i| \le 10^9)~

• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy hoán vị ~p_1,p_2,...,p_n~

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị của đoạn con gồm các phần tử liên tiếp chưa có phần tử nào bị xóa và có tổng lớn nhất trước bước thứ ~i~.

Scoring

• Subtask ~1~ (~30~ điểm): ~n \le 5000~

• Subtask ~2~ (~30~ điểm): ~a_i > 0~

• Subtask ~3~ (~40~ điểm): Không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

7
6
4
3
3
2
2

Notes

• Trước khi thực hiện thao tác ~1~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~-2~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,7]~

• Trước khi thực hiện thao tác ~2~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,5]~

• Trước khi thực hiện thao tác ~3~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[5,5]~

• Trước khi thực hiện thao tác ~4~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~

• Trước khi thực hiện thao tác ~5~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~

• Trước khi thực hiện thao tác ~6~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~

• Trước khi thực hiện thao tác ~7~, dãy là [~*~, ~*~, ~2~, ~*~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~

Cho một vườn hoa ~N \times M~, mỗi ô là một bông hoa có chiều cao là ~H_{i, j}~. Chiều cao của các bông hoa đều phân biệt. Ông chủ muốn chọn một hình chữ nhật các bông hoa sao cho chiều cao của bông hoa nằm ở góc trái trên và góc phải dưới cao hơn hẳn chiều cao của các bông hoa còn lại trong hình chữ nhật.

Một hình chữ nhật có hai góc là ~(x_1, y_1)~ và ~(x_2, y_2)~ với ~1 \le x_1 \le x_2 \le N~ và ~1 \le y_1 \le y_2 \le M~ thỏa mãn khi với mọi ~x_3~, ~y_3~ sao cho ~x_1 \le x_3 \le x_2~, ~y_1 \le y_3 \le y_2~:

~H_{x_3, y_3} \le min(H_{x_1, y_1}, H_{x_2, y_2})~

Vì vườn hoa rất lớn hãy giúp ông chủ đếm có bao nhiêu hình chữ nhật các bông hoa thỏa mãn điều kiện nhé.

Input

• Dòng đầu là ~2~ số nguyên ~N~, ~M~ ~(N \times M \le 10^5, N \le 20)~.
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số ~H_{i, j}~ ~(1 \le H_{i, j} \le N \times M)~.

Output

• In ra một dòng duy nhất là số hình chữ nhật thỏa mãn.

Sample Input 1

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

Sample Output 1

30

Sample Input 2

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

Sample Output 2

26

Scoring

• ~20\%~ số test đầu có ~N \times M \le 1000~.
• ~80\%~ số test còn lại không có điều kiện gì thêm.

Bạn đang đi trong thành phố ~D~, được mô tả bằng hệ trục tọa độ 2D.

Thành phố ~D~ được chia thành ~n~ vùng được mô tả bằng mảng ~a~ độ dài ~n + 1~ với ~a_0 < a_1 < \dots < a_n~, với vùng thứ ~i~ được giới hạn bằng ~2~ đường thẳng ~x = a_{i - 1}~ và ~x = a_i~. Trong vùng thứ ~i~, bạn chỉ được chạy với tốc độ tối đa là ~v_i\ km/h~.

Bạn đang ở ~A(x_1, y_1)~ nằm trong vùng ~1~ và cần tới ~B(x_2, y_2)~ nằm trong vùng ~n~.

Biết rằng, một đơn vị độ dài trong hệ trục tọa độ tương ứng với ~1\ km~. Hãy cho biết thời gian nhanh nhất bạn có thể đi từ ~A~ đến ~B~ và bạn không được phép vượt tốc độ ở bất kỳ đâu.

Input

• Dòng đầu gồm một số nguyên dương ~n~ ~(2 \le n \le 10^5)~ là số vùng của thành phố.

• Dòng thứ hai gồm ~n + 1~ số nguyên ~a_0, a_1, \dots, a_n~ ~(0 \le a_i \le 10^9)~ là các giới hạn trong thành phố.

• Dòng thứ ba gồm ~n~ số nguyên ~v_1, v_2, \dots, v_n~ ~(1 \le v_i \le 10^9)~ mô tả tốc độ tối đa được chạy trong các vùng.

• Dòng thứ ba nhập vào bốn số nguyên ~x_1, y_1, x_2, y_2~ ~(a_0 \le x_1, x_2 \le a_n, 0 \le y_1, y_2 \le 10^9)~ mô tả hai điểm ~A(x_1, y_1)~ và ~B(x_2, y_2)~.

Output

In ra thời gian nhanh nhất bạn có thể đi từ ~A~ đến ~B~ nếu bạn không được phép vượt tốc độ.

Đáp án của bạn sẽ được chấp nhận nếu không chênh lệch với đáp án của ban tổ chức nhiều hơn ~10^{-6}~.

Scoring

• Subtask ~1~ (~30~ điểm) : ~n = 2~.

• Subtask ~2~ (~70~ điểm) : Không có ràng buộc gì thêm.

Sample Input 1

2
0 5 8
6 1
1 2 5 7

Sample Output 1

1.0671874

Lanhf và FireGhost đi mua sắm ở một cửa hàng ma thuật. Cửa hàng có ~n~ món đồ được đánh số từ ~1~ đến ~n~, món đồ thứ ~i~ có độ hấp dẫn là ~c_i~ và giá tiền là ~v_i~.

Hai người họ muốn mua một bộ sưu tập các món đồ, nhưng với một điều kiện kì lạ. Gọi ~S=\{s_1,s_2,\ldots,s_p\}~ (~1\le s_i\le n~) là bộ sưu tập họ đã mua:

1. Với mọi ~T=\{t_1,t_2,\ldots,t_q\}~ là một tập con khác rỗng của ~S~, ta có ~c_{t_1}\oplus c_{t_2}\oplus\ldots\oplus c_{t_q}\ne 0~. Ở đây ~\oplus~ chỉ phép thao tác bit XOR.

2. Tập ~S~ có lực lượng lớn nhất trong tất cả các tập thoả mãn điều kiện trên.

Có thể có rất nhiều bộ sưu tập thoả mãn, tuy nhiên Lanhf thích tập ~A~ còn FireGhost thích tập ~B~. Để thuyết phục FireGhost chọn tập ~A~, Lanhf quyết định thay đổi giá tiền của các món đồ. Cụ thể, với mỗi món đồ ~i~ cậu ta có thể tiêu hao ~(x-v_i)^2~ mana để thay đổi giá tiền của nó thành một số nguyên không âm ~x~. Mối món đồ chỉ có thể bị thay đổi giá trị tối đa ~1~ lần.

Lanhf mong rằng có thể thay đổi giá tiền sao cho tập ~A~ trở thành tập có giá tiền nhỏ nhất và tập ~B~ trở thành tập có giá tiền lớn nhất trong tất cả các bộ sưu tập thoả mãn (giá tiền của bộ sưu tập là tổng giá tiền các món đồ ở trong nó). Hãy giúp Lanhf thực hiện mong muốn của mình với lượng mana tiêu hao ít nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~p~ (~1\le p\le n\le 1000~, ~p\le 64~) — số món đồ trong cửa hàng và kích thước của tập ~A~ và ~B~.

• Dòng thứ hai gồm ~n~ số nguyên ~c_1,c_2,\ldots,c_n~ (~1\le c_i<2^{64}~) — độ hấp dẫn của các món đồ.

• Dòng thứ ba gồm ~n~ số nguyên ~v_1,v_2,\ldots,v_n~ (~0\le v_i\le 10^6~) — giá tiền của các món đồ.

• Dòng thứ tư gồm ~p~ số nguyên phân biệt ~a_1,a_2,\ldots,a_p~ (~1\le a_i\le n~) — các phần tử của tập ~A~.

• Dòng thứ năm gồm ~p~ số nguyên phân biệt ~b_1,b_2,\ldots,b_p~ (~1\le b_i\le n~) — các phần tử của tập ~B~.

Dữ liệu đảm bảo ~A~ và ~B~ là hai bộ sưu tập hợp lệ.

Output

In ra một số nguyên là lượng mana ít nhất mà Lanhf cần dùng dể đạt được mong muốn.

Scoring

• Subtask ~1~ (~15~ điểm): ~n\le 10~, ~p\le 4~, ~1\le v_i\le 5~.

• Subtask ~2~ (~15~ điểm): ~n\le 50~, ~p\le 2~, ~1\le v_i\le 10~.

• Subtask ~3~ (~20~ điểm): ~n\le 500~, ~p\le 30~, ~0\le v_i\le 1~.

• Subtask ~4~ (~10~ điểm): Hai tập ~A~ và ~B~ trùng nhau.

• Subtask ~5~ (~40~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

6

Notes

Ở test ví dụ trên, các bộ sưu tập hợp lệ là ~\{1,2,3\}~, ~\{1,2,4\}~, ~\{1,2,5\}~, ~\{1,3,4\}~, ~\{1,3,5\}~, ~\{2,3,4\}~, ~\{2,4,5\}~, ~\{3,4,5\}~. Phương án tối ưu sẽ thay đổi: ~v_3 = 2~, ~v_1 = v_2 = v_4 = v_5 = 3~.