Đào là một chuyên gia bẻ khóa, đang đối mặt với một két sắt cổ điển có một kim quay trên mặt đồng hồ 100 vị trí, được đánh số từ ~0~ đến ~99~. Kim luôn bắt đầu ở vị trí ~0~. Mật khẩu két được mã hóa từ một dãy các thao tác quay ~N~ lần. Mỗi thao tác là một lệnh quay ~L~ (trái) hoặc ~R~ (phải) kèm theo số lần quay ~x~. Mật khẩu cuối cùng của két sắt là tổng số lần kim quay chạm vào vị trí ~0~ trong suốt quá trình thực hiện chuỗi lệnh (bao gồm cả trường hợp kim dừng lại chính xác tại vị trí ~0~). Bạn hãy giúp Đào tính toán mật khẩu này.

Input

Dòng đầu tiên là một số nguyên dương ~N~ (số lượng thao tác).

~N~ dòng tiếp theo, mỗi dòng mô tả một thao tác quay:

• ~L \space x~: Quay kim sang trái ~x~ lần.

• ~R \space x~: Quay kim sang phải ~x~ lần.

Dữ liệu đảm bảo ~1 \leq x \leq 10^5~ trong mọi thao tác quay.

Output

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

Scoring

Sample Input 1

5
L 5
R 10
L 5
R 120
L 40

Sample Output 1

4

Sample Input 2

1
R 500

Sample Output 2

5

Notes

Giải thích test ví dụ 1:

Ban đầu, kim ở vị trí ~0~.

• Sau lần quay ~L \space 5~, kim dừng ở vị trí ~95~.

• Sau lần quay ~R \space 10~, kim dừng ở vị trí ~5~, đi qua vị trí ~0~ một lần.

• Sau lần quay ~L \space 5~, kim dừng ở vị trí ~0~, kim chỉ đúng vị trí ~0~.

• Sau lần quay ~R \space 120~, kim dừng ở vị trí ~20~, đi qua vị trí ~0~ một lần.

• Sau lần quay ~L \space 40~, lúc này kim dừng ở vị trí ~80~, đi qua vị trí ~0~ một lần.

Đáp án: 4.

Giải thích test ví dụ 2:

• Ban đầu, kim ở vị trí ~0~.

• Sau lần quay duy nhất, nó đi qua vị trí ~0~ đúng 4 lần và dừng ở đó vào cuối thao tác.

Đáp án: 5.

Quân có ~N~ bóng đèn được đặt trên một hàng ngang và được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải. Bóng đèn thứ ~i~ đang ở trạng thái ban đầu là ~S_i = 0 / 1~, với ~0~ có nghĩa là tắt và ~1~ là bật. Quân sau đó sẽ thực hiện thao tác sau ~K~ lần:

• Đầu tiên, Quân tìm tập ~A~ là tập các bóng đèn ~i~ hiện tại thỏa mãn ~1 < i < N~ và đèn thứ ~i - 1~ và ~i + 1~ đều được bật.

• Sau đó Quân đồng thời thay đổi trạng thái của các bóng đèn trong tập ~A~ (từ bật thành tắt, từ tắt thành bật).

Cho ~N~, ~K~ và trạng thái các bóng đèn ban đầu, bạn hãy tìm trạng thái của các bóng đèn sau khi Quân thực hiện ~K~ thao tác.

Input

Dòng đầu chứa hai số nguyên ~N~, ~K~ (~1 \le N \le 2~ x ~10 ^ 5~, ~1 \le K \le 10^9~).

Dòng sau chứa một xâu nhị phân ~S~ gồm đúng ~N~ kí tự là trạng thái ban đầu của các bóng đèn.

Output

In ra một xâu gồm ~N~ kí tự là trạng thái của các bóng đèn sau ~K~ thao tác.

Scoring

Sample Input 1

6 2
110111

Sample Output 1

100111

Sample Input 2

5 3
10101

Sample Output 2

10001

Notes

Ở test ví dụ 1:

• Ban đầu: ~110111~

• Sau thao tác đầu tiên: ~111101~

• Sau thao tác thứ hai: ~100111~

Vậy đáp án là ~100111~

Ở test ví dụ 2:

• Ban đầu: ~10101~

• Sau thao tác đầu tiên: ~11111~

• Sau thao tác thứ hai: ~10001~

• Sau thao tác thứ ba: ~10001~

Vậy đáp án là ~10001~

Cho bốn dãy số nguyên dương độ dài ~N~ lần lượt ~A_1, A_2, \cdots, A_N~, ~B_1, B_2, \cdots, B_N~, ~C_1, C_2, \cdots, C_N~ và ~D_1, D_2, \cdots, D_N~. Bốn dãy số nguyên này cho biết độ hấp dẫn của các màn chơi trong máy chơi game ~A, B, C~ và ~D~.

Trong một lượt chơi, bạn phải chơi mỗi máy đúng một lần, và mỗi lần bạn phải chọn ra một màn chơi của mỗi máy chơi game. Gọi ~i, j, k, l~ lần lượt là các màn chơi được chọn trong trò chơi ~A, B, C~ và ~D~, bạn sẽ nhận được mức độ vui vẻ bằng ~(A_i + B_j + C_k + D_l)^{67}~.

Nếu bắt bạn tìm bộ bốn màn chơi cho ra được "mức độ vui vẻ" cao nhất thì nó lại quá dễ, nên badeo sẽ bắt bạn tìm các màn chơi trong 4 máy chơi game sao cho mức độ vui vẻ của màn chơi này lớn thứ ~K~ trong số tất cả các bộ ~4~ màn chơi bạn có thể chọn.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~K~.

Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \cdots, A_N~.

Dòng thứ ba gồm ~N~ số nguyên dương ~B_1, B_2, \cdots, B_N~.

Dòng thứ tư gồm ~N~ số nguyên dương ~C_1, C_2, \cdots, C_N~.

Dòng thứ năm gồm ~N~ số nguyên dương ~D_1, D_2, \cdots, D_N~.

Output

Gồm một dòng nguyên bao gồm các giá trị ~A_i, B_j, C_k, D_l~ có mức độ vui vẻ lớn thứ ~K~.

Nếu có cùng nhiều bộ ~4~ giá trị, thì bộ bất kỳ đáp án cho ra cùng mức độ vui vẻ cũng sẽ được chấp nhận.

Scoring

Trong mọi testcase, điều kiện sau luôn thỏa ~1 \leq K \leq \min(N^4, 2 \cdot 10^5)~.

Gọi ~M~ là giá trị nguyên dương lớn nhất xuất hiện trong các số ~A_i, B_j, C_k, D_l~.

Sample Input 1

4 1
1 2 3 4
6 7 667 67
67 69 78 789
1 2 3 4

Sample Output 1

4 667 789 4

Sample Input 2

4 4
1 2 3 4
6 7 667 67
67 69 78 789
1 2 3 4

Sample Output 2

3 667 789 3

Trong toán học, người ta định nghĩa trung vị của một dãy số độ dài ~n~ là phần tử thứ ~\left\lfloor \dfrac{n+1}{2} \right\rfloor~ sau khi sắp xếp các số theo thứ tự không giảm. Ta định nghĩa hai dãy số tương đồng là hai dãy số có trung vị bằng nhau.

Yêu cầu: Cho một dãy ~n~ số nguyên không âm ~a_1,a_2, \ldots,a_n~; bạn hãy tính số dãy con của dãy số đã cho đồng dạng với nó. Một dãy ~b~ được gọi là dãy con của ~a~ nếu có thể thu được ~b~ bằng cách xóa đi một số phần tử ở đầu và ở cuối (Có thể không xóa số nào).

Input

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

Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1,a_2,\ldots ,a_n~ (~a_i \le 10^9~) mô tả dãy số được cho. Các số cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là số dãy con đồng dạng với dãy ban đầu.

Scoring

Sample Input 1

6
1 7 7 0 1 3

Sample Output 1

11

Sample Input 2

4
3 2 3 5

Sample Output 2

6

Notes

Trong test ví dụ một, trung vị của dãy số được cho là 1. Các dãy đồng dạng với dãy được cho là: ~[1]~, ~[1]~, ~[1, 7]~, ~[1, 3]~, ~[7, 0, 1]~, ~[0, 1, 3]~, ~[1, 7, 7, 0]~, ~[7, 7, 0, 1]~, ~[7, 0, 1, 3]~, ~[1, 7, 7, 0, 1]~, ~[1, 7, 7, 0, 1, 3]~.

Trong test ví dụ hai, trung vị của dãy số được cho là 3 (dãy sắp xếp là ~2, 3, 3, 5~, phần tử thứ ~\lfloor \frac{4+1}{2} \rfloor = 2~ là 3). Các dãy đồng dạng với dãy được cho là: ~[3]~, ~[3]~, ~[3, 5]~, ~[3, 2, 3]~, ~[2, 3, 5]~, ~[3, 2, 3, 5]~.

Cho dãy số nguyên dương ~A_1, A_2, \cdots, A_N~ (~N~ là số chẵn). Giá trị ~A_i~ tương ứng độ năng động của người thứ ~i~. Ta cần chọn ra ~N/2~ cặp đôi để nhảy sao cho mỗi người thuộc đúng một cặp, mỗi cặp có hai người. Gọi ~N/2~ cặp chia được là ~(i_1, j_1), (i_2, j_2), \cdots, (i_{N/2}, j_{N/2})~, khi đó ta định nghĩa "độ thiếu ăn ý" trong một cặp ~(i_k, j_k)~ là ~|A_{i_k} - A_{j_k}|~. Bạn muốn chọn ra ~N/2~ cặp sao cho tổng độ thiếu ăn ý của ~N/2~ cặp là nhỏ nhất có thể. Tuy nhiên bạn lại phát hiện ra ~N/2~ cặp ~(x_i, y_i)~ đặc biệt (họ có thể là "nyc", "cựu mập mờ", hoặc những mối quan hệ nguy hiểm tiềm ẩn!) và sẽ dẫn tới nhiều rủi ro để hai người này nhảy chung nên bạn không được ghép cặp người ~x_i~ với người ~y_i~ lại.

Input

Dòng đầu gồm số nguyên dương ~N~ (~N~ là số chẵn).

Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \cdots, A_N~.

Trong ~N/2~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~x_i, y_i~ là cặp "nguy hiểm" thứ ~i~. Dãy ~x_1, x_2, \cdots, x_{N/2}, y_1, y_2, \cdots, y_{N/2}~ tạo thành một hoán vị của ~\{1, 2, \cdots, N\}~.

Output

Gồm 1 dòng duy nhất gồm tổng độ thiếu ăn ý nhỏ nhất ta có đạt được nếu sắp xếp ~N~ người vào ~N/2~ cặp và không vi phạm vô ~N/2~ cặp nguy hiểm.

Scoring

Trong mọi testcase, điều kiện sau luôn thỏa ~4 \leq N \leq 3 \cdot 10^5, 1 \leq A_i \leq 10^9~.

Sample Input 1

4
1 10 3 4
1 3
2 4

Sample Output 1

10

Sample Input 2

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

Sample Output 2

5

Notes

Ở ví dụ một, ta ghép cặp ~\{1, 2\}~ và ~\{3, 4\}~. Khi đó tổng độ thiếu ăn ý sẽ là ~|10 - 1| + |3 - 4| = 10~.

Ở ví dụ hai, ta ghép gặp ~\{1, 3\}~, ~\{2, 4\}~, và ~\{5, 6\}~. Độ thiếu ăn ý tổng: ~|1 - 3| + |2 - 4| + |5 - 6| = 5~.

Phố Dải Lụa sắp khai mạc "Vũ Điệu Sắc Màu". Dọc phố có ~N~ nhóm nghệ sĩ xếp hàng (~1\leq N \leq 2 \cdot 10^5~), nhóm thứ ~i~ mang mức độ khuấy động là ~A_i~ (~1 \leq A_i \leq 10^9~).

Trong một buổi trình diễn của các nghệ sĩ có chỉ mang mức độ khuấy động là ~B_1, B_2, \cdots, B_{2m}~, đội ngũ của bạn dàn dựng đúng ~m~ tiết mục, mỗi tiết mục bạn sẽ chọn ra hai nghệ sĩ kề nhau, khi đó Điểm Sôi Động (ký hiệu ~S~ của buổi biểu diễn) sẽ tăng lên ~|B_i - B_{i+1}|~ (Với ~1 \leq i < 2m~ là thứ tự của người nghệ sĩ có chỉ số nhỏ hơn). Sau mỗi tiết mục, hai người nghệ sĩ vừa trình diễn sẽ rời sân khấu, để phần còn lại cho những nghệ sĩ còn lại, khoảng trống giữa hai người vừa rời đi sẽ được những người nghệ sĩ ở hai bên dồn lại (vẫn giữ thứ tự).Bạn muốn buổi trình diễn phải tuyệt vời nhất có thể nên tổng ~S~ sau cùng phải là lớn nhất có thể.

Ban tổ chức nhận được ~Q~ yêu cầu trình diễn trên các chặng phố khác nhau (~Q \leq 2 \cdot 10^5~). Mỗi yêu cầu là một đoạn ~[l, r]~ (độ dài chẵn), tức là chỉ đạo đội ngũ bạn dàn dựng tiết mục trên dãy con ~B = A_l, A_{l+1}, \ldots, A_{r}~. Với mỗi yêu cầu, bạn cần cho biết Điểm Sôi Động tối đa bạn có thể đạt được là bao nhiêu.

Input

Dòng đầu gồm hai số nguyên dương ~N~ và ~Q~ tương ứng với số nghệ sĩ hiện tại của bạn và số yêu cầu trình diễn.

Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_{N}~ tương ứng với mức độ khuấy động của các nghệ sĩ.

~Q~ Dòng tiếp theo gồm hai số nguyên dương ~l~ và ~r~ tương ứng với một yêu cầu trình diễn của các nghệ sĩ ~A_l, A_{l + 1}, \ldots, A_r~. (Đảm bảo ~1 \leq l \leq r \leq N~ và ~r - l + 1~ là một số chẵn)

Output

Gồm ~Q~ số nguyên dương, với số thứ ~i~ cho biết Điểm Sôi Động tối đa bạn có thể đạt được nếu sắp xếp các tiết mục tối ưu và hấp dẫn.

Scoring

Sample Input 1

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

Sample Output 1

6
11

Notes

Trong truy vấn đầu tiên dãy ~B = [1, 5, 4, 2]~ :

• Ta chọn tiết mục đầu tiên gồm nghệ sĩ thứ tự ~1~ và ~2~, sau đó dãy ~B = [4, 2]~.

• Ta chỉ còn đúng một cách chọn giữa nghệ sĩ thứ tự ~1~ và ~2~ (đã được đánh số lại), sau đó dãy ~B~ rỗng

• Như vậy ta nhận được ~S = |1-5| + |4-2| = 6~

Trong truy vấn thứ hai dãy ~B = [1, 5, 4, 2, 6, 7]~

• Ta chọn tiết mục đầu tiên gồm nghệ sĩ thứ ~2~ và ~3~, sau đó dãy ~B = [1, 2, 6, 7]~

• Ta chọn tiết mục thứ hai gồm nghệ sĩ thứ ~2~ và ~3~ (được đánh số lại), sau đó dãy ~B = [1, 7]~

• Ta chỉ còn đúng một cách chọn giữa nghệ sĩ thứ tự ~1~ và ~2~ (đã được đánh số lại), sau đó dãy ~B~ rỗng

• Như vậy ta nhận được ~S = |4-5| + |2-6| + |1-7| = 11~