Trên con đường dẫn vào thành phố du lịch nổi tiếng, có một hàng cây được trồng ven đường gồm ~n~ cây được đánh số lần lượt từ ~1~ đến ~n~ theo chiều từ đầu đến cuối con đường, trong đó cây thứ ~i~ có chiều cao là ~h_i~.

Để thu hút khách du lịch, chính quyền thành phố muốn cải tạo hàng cây sao cho hấp dẫn nhất. Chính quyền đưa ra các phương án và cần đánh giá các phương án để lựa chọn. Cụ thể, với mỗi phương án được mô tả bằng hai số ~L, R~, khi đó các cây có chiều cao nằm ngoài khoảng ~[L, R]~ sẽ bị loại bỏ và để đánh giá phương án có khả thi hay không cần tính tổng chênh lệch chiều cao giữa hai cây liên tiếp được giữ lại.

Yêu cầu: Cho biết chiều cao của ~n~ cây và ~q~ phương án, hãy lập trình đưa ra tổng chênh lệch chiều cao giữa hai cây liên tiếp còn được giữ lại trong mỗi phương án.

Input:

• Dòng đầu chứa số nguyên ~n, q~ (~1 \le n, q \le 2 \times 10^5~)
• Dòng thứ hai chứa ~n~ số nguyên ~h_i~ (~1 \le h_i \le 10^9~)
• Tiếp theo là ~q~ dòng, dòng thứ ~j~ chứa hai số nguyên ~L_j, R_j~ (~1 \le L_j \le R_j \le 10^9~) mô tả một phương án.

Output:

Với mỗi phương án đưa ra kết quả trên một dòng là tổng chênh lệch chiều cao giữa hai cây liên tiếp còn được giữ lại

Subtask 1 (20%): ~n, q \le 5000~;
Subtask 2 (20%): ~h_i \le 400~;
Subtask 3 (20%): ~L_j \le L_{j + 1}, R_j \le R_{j + 1}~;
Subtask 4 (20%): ~n, q \le 7 \times 10^4~;
Subtask 5 (20%): Không có ràng buộc gì thêm.

Một khu hội chợ có dạng là một hình đa giác đều gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Ban tổ chức chia khu hội chợ bằng ~n - 3~ đường ngăn để nhận được ~n - 2~ gian hàng đều có hình tam giác, các đường ngăn không giao nhau bên trong đa giác, đường ngăn thứ ~k~ đi qua hai đỉnh phân biệt ~i_k, j_k~ (~1 \le k \le n - 3~). Như vậy, một gian hàng sẽ có ba mặt, mỗi mặt là cạnh đa giác hoặc là đường ngăn. Để khuyến khích khách tham quan các gia hàng, Ban tổ chức sẽ có các phần thưởng giá trị ~t_k~ cho khách khi đi qua đường ngăn thứ ~k~.

Alice dự định đi vào khu hội chợ từ một gian hàng có mặt là cạnh nối đỉnh ~u~ và đỉnh ~(u \% n + 1)~ và đi ra khỏi khu hội chợ từ một gian hàng có mặt là cạnh nối đỉnh ~v~ và đỉnh ~(v \% n + 1)~. Alice mong muốn mỗi gian hàng sẽ đi qua không quá một lần và tổng giá trị các phần thưởng nhận được là lớn nhất. Chú ý rằng ~u \ne v~ và phép toán ~\%~ là phép toán chia lấy dư.

Yêu cầu: Alice có ~q~ giả định, mỗi giả định mô tả bằng hai số nguyên ~u, v~ có nghĩa là Alice đi vào từ cạnh nối đỉnh ~u~ và đỉnh ~(u \% n + 1)~ và đi ra từ cạnh nối đỉnh ~v~ và đỉnh ~(v \%n + 1)~, với mỗi giả định hãy giúp Alice tính tổng giá trị các phần thưởng nhận được là lớn nhất có thể đạt được.

Input:

• Dòng đầu chứa hai số nguyên dương ~n, q~ (~q \le n~);
• Dòng thứ ~k~ (~1 \le k \le n - 3~) chứa ba số nguyên dương ~i_k, j_k, t_k~ mô tả đường ngăn thứ ~k~ (~1 \le i_k, t_k \le n~ và ~i_k \ne j_k; t_k \le 10^9~);
• Dòng thứ ~s~ (~1 \le s \le q~) gồm hai số nguyên dương ~u, v~ mô tả một giả định.

Output:

• Ghi ra ~q~ dòng, mỗi dòng chứa một số nguyên là tổng giá trị các phần thưởng nhận được là lớn nhất có thể đạt được.

Subtask 1 (40%): ~n \le 10~;
Subtask 2 (30%): ~n \le 100~;
Subtask 3 (30%): ~n \le 10^5~;

Xét tập ~A~ gồm ~n~ xâu, mỗi xâu độ dài ~m~ và chỉ gồm các ký tự "0", "1" hoặc "*". Với một xâu, ta có thể biến đổi để nhận được xâu nhị phân bằng cách thay thế mỗi ký tự "*" trong xâu thành ký tự "0" hoặc "1". Biến đổi ~n~ xâu của tập ~A~ để nhận được tập xâu nhị phân ~B~ có lực lượng nhỏ nhất. Biến đổi ~n~ xâu của tập ~A~ để nhận được tập xâu nhị phân ~C~ có lực lượng lớn nhất.

Yêu cầu: Cho ~n~ xâu, tìm cách biến đổi ~n~ xâu để nhận được tập xâu nhị phân ~B~ có lực lượng nhỏ nhất và tập xâu nhị phân ~C~ có lực lượng lớn nhất.

Input:

• Dòng đầu chứa hai số nguyên dương ~n, m~ (~m \le 100~);
• ~m~ dòng sau, mỗi dòng một xâu độ dài ~m~ chỉ gồm các ký tự "0", "1" hoặc "*" mô tả ~n~ xâu của tập ~A~.

Output

• Dòng đầu là số nguyên là lực lượng của tập ~B~; tiếp theo là ~n~ xâu nhị phân mô tả cách biến đổi từng xâu để nhận được tập ~B~, các đại lượng cách nhau đúng một dấu cách;
• Dòng thứ hai là số nguyên là lực lượng của tập ~C~; tiếp theo là ~n~ xâu nhị phân mô tả cách biến đổi từng xâu để nhận được tập ~C~, các đại lượng cách nhau đúng một dấu cách.

Cách tính điểm:

Có ~20~ test, mỗi test ~5.0~ điểm. Gọi ~s_B, s_C~ tương ứng là lực lượng của tập ~B, C~ do thí sinh tìm được và kết quả của Ban giám khảo tương ứng là ~w_B, w_C~, khi đó số điểm bạn đạt được cho mỗi test là ~2.5 \times min\{1, (\frac{w_B}{s_B})^5 \} + 2.5 \times min\{1, (\frac{w_C}{s_C})^5 \}~.

Subtask 1 (50%): ~n \le 10~;
Subtask 2 (50%): ~n \le 1000~.