Cho mảng ~a~ gồm ~n~ phần tử. Ban đầu, các phần tử đều có giá trị là ~0~.

Có ~q~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~l~, ~r~, ~x~ với ý nghĩa: xét đoạn con liên tiếp từ ~l~ đến ~r~ trên mảng ~a~, tăng ~a_i~ lên một lượng ~x \times (i - l + 1)~ với ~l \le i \le r~.

Hãy in ra tổng của các phần tử trong mảng ~a~ sau ~q~ truy vấn.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ và ~q~ (~1 \le n \le 2 \times 10^8~, ~1 \le q \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l~, ~r~ và ~x~ (~1 \le l \le r \le n~, ~1 \le x \le 10^9~).

OUTPUT

Dòng duy nhất là tổng các phần tử trong mảng ~a~ sau khi thực hiện ~q~ truy vấn.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~20032024~.

SAMPLE INPUT

5 3
1 2 1
2 3 1
3 5 2

SAMPLE OUTPUT

18

Mảng sau khi thực hiện tất cả các truy vấn là ~[1, 3, 4, 4, 6]~.

SUBTASKS

Đây là một bài toán tương tác. Bạn có thể tham khảo hướng dẫn làm bài tương tác tại đây.

Cho hai túi kẹo, túi thứ nhất có ~x~ viên kẹo, túi thứ hai có ~y~ viên kẹo.

duong3982 và noodles0428 sẽ chơi một trò chơi với nhau. Mỗi lượt, duong3982 và noodles0428 có hai lựa chọn: bốc một viên kẹo ở một trong hai túi, hoặc bốc một viên kẹo ở cả hai túi.

Người đầu tiên không thể thực hiện lượt đi của mình là người thua cuộc.

Bạn sẽ trong vai noodles0428, và bạn có thể quyết định bạn muốn đi trước hay đi sau. Hãy tìm chiến thuật để noodles0428 luôn thắng và khiến cho duong3982 phải tặng quà cho cô ấy!

TƯƠNG TÁC

Đầu tiên, bạn cần đọc vào hai số nguyên dương ~x~ và ~y~ (~1 \le x, y \le 20000~) từ đầu vào chuẩn.

Sau đó, bạn cần in ra một số nguyên ~0~ hoặc ~1~ tương ứng bạn muốn đi trước hay đi sau.

Lúc này:

• Nếu là lượt của máy chấm: Bạn cần đọc từ đầu vào chuẩn một xâu là A hoặc B hoặc AB, tương ứng với máy chấm bốc một viên kẹo từ túi thứ nhất, túi thứ hai, hoặc cả hai túi.
• Nếu là lượt của bạn: Bạn cần in ra A hoặc B hoặc AB, tương ứng với bốc một viên kẹo từ túi thứ nhất, túi thứ hai, hoặc cả hai túi.

Nếu máy chấm thua, máy chấm sẽ in ra số nguyên ~-1~ duy nhất. Lúc này, chương trình của bạn cần ngắt để nhận Kết quả đúng.

Nếu bạn thua, bạn cần in ra số nguyên ~-1~ duy nhất. Lúc này, chương trình của bạn cần ngắt để nhận Kết quả sai.

SAMPLE

SUBTASKS

giaminh2211 vừa có bài test CP. Nội dung bài toán như sau:

Cho một bảng ~n*m~, ô (~i, j~) chứa một trong ba số nguyên (~0, 1, 2~):

• 0: không tồn tại gì ở ô (~i, j~)
• 1: tồn tại một máy phát ở ô (~i, j~)
• 2: tồn tại một thiết bị điện tử ở ô (~i~, ~j~)

Độ mạnh của máy phát là ~d~. Máy phát tại ô (~i~, ~j~) sẽ phát sóng cho các thiết bị tại vị trí (~x~, ~y~) thỏa mãn khoảng cách Manhattan giữa (~i~, ~j~) và (~x~, ~y~) bé hơn hoặc bằng ~d~.

Hãy tìm ~d~ nhỏ nhất để tất cả thiết bị được phát sóng.

giaminh2211 đã giải được bài toán trên, bạn có thể làm được như vậy không?

Nhắc lại: Khoảng cách Manhattan giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ được tính bằng công thức: ~{Manhattan Distance} = |x_2 - x_1| + |y_2 - y_1|~

INPUT

• Dòng đầu tiên chứa số nguyên dương ~t~ là số test case (~t \le 5~)
• Dòng đầu tiên của mỗi test chứa hai số nguyên ~n~ và ~m~ là kích thước bảng.
• ~n~ dòng tiếp theo của mỗi test, mỗi dòng chứa ~m~ số nguyên mô tả bảng.

OUTPUT

• Với mỗi test case in ra trên một dòng số nguyên ~d~, là độ mạnh nhỏ nhất của máy phát sao cho tất cả thiết bị đều được phát sóng.

SAMPLE INPUT

1
3 3
1 0 1
0 2 0
1 0 1

SAMPLE OUTPUT

2

SUBTASKS

giaminh2211 thích làm bài chung với bạn trong các Codeforces round. Trước khi làm thì phải phân chia nhiệm vụ. giaminh2211 là một đặc vụ FBI nên biết trước độ khó của các bài trong đề thi Codeforces hôm nay.

Hãy giúp giaminh2211 cần phân chia nhiệm vụ với partner sao cho chênh lệch tổng độ khó là nhỏ nhất

Lưu ý: Số lượng bài hai người làm không nhất thiết bằng nhau.

INPUT

Dòng đầu chứa số nguyên dương ~n~ (~n \le 10^5~) là số bài trong kì thi Codeforces ngày hôm nay.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ... a_n~ là độ khó của các bài của kì thi ngày hôm nay. (~1 \le a_i \le 10^5~, ~\sum a_i \le 10^5~).

OUTPUT

Dòng thứ nhất ghi chênh lệch nhỏ nhất trong cách chia bài tối ưu.

Dòng thứ hai ghi ra các chỉ số bài mà giaminh2211 sẽ làm trong cách chia bài tối ưu.

Nếu có nhiều cách chia, bạn chỉ cần in ra một cách bất kì.

SAMPLE INPUT

8 
800 800 1000 1000 1300 1300 1700 1750

SAMPLE OUTPUT

50
2 4 6 8

Một cách chia tối ưu là giaminh2211 làm bài ~2, 4, 6, 8~.

SUBTASKS

Sau kỳ thi VOI, duong3982 quyết định không thi VOI nữa mà chuyển qua thi ICPC. Để thi ICPC thì phải học đồ thị, và duong3982 đang học mảng này.

duong3982 đã tìm thấy ~n~ bài tập, và độ khó của mỗi bài lần lượt là ~a_1, a_2, ..., a_n~. Ngoài ra, vì đồ thị là một mảng khá rộng lớn, anh ấy cũng đã tìm thấy ~m~ kỹ năng liên quan. Các kỹ năng có độ khó lần lượt là ~b_1, b_2, ..., b_m~.

Hiện tại, sức mạnh của duong3982 đang là ~1~, và giả sử sức mạnh của duong3982 đang là ~x~, thì để làm bài tập thứ ~i~, duong3982 sẽ cần thời gian là ~\lceil \frac {a_i}{x} \rceil~ giờ. Tuy nhiên, giữ nguyên sức mạnh là ~1~ có thể khiến việc luyện tập trở nên khó khăn. duong3982 có thể cải thiện sức mạnh của mình, bằng cách rèn luyện ~m~ kỹ năng ở trên.

Vì càng đào sâu các kỹ năng thì càng khó, nên khi duong3982 rèn luyện kỹ năng thứ ~i~ ở lần thứ ~x~ bất kỳ, thì duong3982 sẽ cần ~x! \times b_i~ giờ. Sau khi rèn luyện, sức mạnh của duong3982 sẽ được tăng lên ~1~ đơn vị.

Yêu cầu: Hãy tìm thời gian tối thiểu để duong3982 hoàn thành ~n~ bài tập nói trên.

INPUT

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 10^5~) tương ứng số bài tập và số kỹ năng.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) là độ khó của từng bài tập.

Dòng thứ ba gồm ~n~ số nguyên dương ~b_1, b_2, ..., b_m~ (~1 \le b_i \le 10^9~) là độ khó của từng kỹ năng.

OUTPUT

Một số nguyên dương duy nhất, là số giờ duong3982 cần để hoàn thành ~n~ bài tập.

SAMPLE INPUT

3 2
10 20 1
2 3

SAMPLE OUTPUT

17

Một trình tự tối ưu là rèn luyện kỹ năng ~1~, rèn luyện kỹ năng ~2~, sau đó làm bài tập ~1~, bài tập ~2~ và bài tập ~3~. Tổng thời gian cần có là ~17~ giờ.

SUBTASKS

Dựa trên một câu chuyện chưa có thật...

Sau gần ~1~ năm thành lập, ClueOJ đã sở hữu trên ~1500~ người dùng. duong3982 đã chọn ra ~1500~ người may mắn nhất tham gia một trò chơi. Sau nhiều vòng loại, còn lại ~n~ người chơi ở vòng cuối cùng.

Trước mặt mỗi người chơi lúc này là một số viên kẹo, người thứ ~i~ sở hữu ~a_i~ viên kẹo. Lúc này, duong3982 muốn chọn ra một vài người chơi, thỏa mãn tồn tại một số nguyên ~x \ge 2~, sao cho số kẹo của từng người đều có thể chia đều ra ~x~ phần. Những người được chọn sẽ được duong3982 trả thưởng: một viên kẹo (mà người chơi đó có) tương ứng với ~1~ ~VND~.

Yêu cầu: Trong trường hợp xấu nhất, hãy tìm tổng giá trị phần thưởng mà duong3982 phải trả.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 1500~) là số người chơi còn lại ở vòng cuối cùng.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^{18}~) là số viên kẹo còn lại của mỗi người chơi.

OUTPUT

Dòng duy nhất là số tiền duong3982 phải trả trong trường hợp xấu nhất.

SAMPLE INPUT

5
2 4 9 7 14

SAMPLE OUTPUT

21

Hai người chơi được chọn là người chơi thứ tư và thứ năm, và tổng số tiền duong3982 phải trả là ~7 + 14 = 21~.

SUBTASKS

NATO, hay Tổ chức Hiệp ước Bắc Đại Tây Dương, là một liên minh quân sự được thành lập vào năm 1949. Đây là một tập hợp các quốc gia từ Bắc Mỹ và châu Âu, ban đầu với mục tiêu chính là đối trọng với sức mạnh và tầm ảnh hưởng của Liên Xô sau Thế chiến II. Nền tảng của NATO là Hiệp ước Bắc Đại Tây Dương, một văn kiện quan trọng xác định các nguyên tắc hoạt động của liên minh. Một trong những điều khoản cốt lõi là Điều 5, một cam kết về phòng thủ tập thể, nghĩa là một cuộc tấn công vũ trang chống lại một quốc gia thành viên sẽ được coi là một cuộc tấn công chống lại tất cả các thành viên. Trong suốt thời kỳ Chiến tranh Lạnh, NATO là một yếu tố răn đe quan trọng, góp phần duy trì sự ổn định giữa hai siêu cường. Sau sự sụp đổ của Liên Xô, NATO đã trải qua quá trình mở rộng và điều chỉnh vai trò, tham gia vào các hoạt động gìn giữ hòa bình, can thiệp nhân đạo và đối phó với các thách thức an ninh mới trên toàn cầu. Ngày nay, NATO vẫn là một liên minh quân sự mạnh với nhiều quốc gia thành viên, tiếp tục đóng vai trò quan trọng trong việc đảm bảo an ninh khu vực và quốc tế.

Tiền thân của NATO: Hiệp ước Brussels là một hiệp ước bảo vệ lẫn nhau giữa các nước Tây Âu để chống lại mối đe dọa ngày càng tăng từ Liên Xô sáng lập vào đầu Chiến tranh Lạnh. Nó được ký kết vào ngày 17 tháng 3 năm 1948 bởi Bỉ, Hà Lan, Luxembourg, Pháp và Vương quốc Anh. Đó là tiền thân của NATO. Mối đe dọa từ Liên Xô trở nên thực sự đáng lo ngại sau vụ phong tỏa Berlin năm 1948, dẫn đến việc thành lập một tổ chức quốc phòng đa quốc gia giữa các nước Tây Âu, Tổ chức Quốc phòng Liên hiệp Phương Tây, vào tháng 9 năm 1948. Tuy nhiên, các nước thành viên của tổ chức lúc đó quá yếu về quân sự để có thể chống lại Lực lượng Vũ trang Liên Xô. Bên cạnh đó, tại Tiệp Khắc vào năm 1948 một cuộc đảo chính của những người cộng sản đã diễn ra thành công và Ngoại trưởng Anh Ernest Bevin tin rằng cách tốt nhất để ngăn chặn các quốc gia khác rơi vào tình trạng như Tiệp Khắc đó là phát triển một chiến lược quân sự giữa các nước phương Tây. Ông có một buổi điều trần tiếp nhận tại Hoa Kỳ, đặc biệt là xem xét sự lo lắng của Mỹ đối với Ý và Đảng Cộng sản Ý.

~n~ quốc gia của NATO đang cần tổ chức họp trong ~q~ ngày để đối phó với một số vấn đề: Tình hình xung đột ở Ukraine, giá nhiên liệu tăng cao, bất đồng quan điểm trong việc ngoại giao với Nga, hay mới nhất là Mỹ áp thuế đối ứng lên hàng hóa thế giới, ...

Trụ sở của các quốc gia thành viên có thể được biểu diễn bằng một đường thẳng, văn phòng của nước thứ ~i~ được đặt tại tọa độ ~x_i~ trên đường thẳng đó. Vào ngày thứ ~k~, các quốc gia từ ~l_k~ đến ~r_k~ sẽ cần gặp mặt để bàn bạc. Họ muốn chọn một tọa độ ~X~ sao cho tổng khoảng cách từ ~X~ đến trụ sở của các quốc gia từ ~l_k~ đến ~r_k~ là nhỏ nhất.

Là một thành viên ẩn của tổ chức, giaminh2211 cần phải tìm ra khoảng cách nhỏ nhất đó để sắp xếp cuộc họp.

INPUT

Dòng đầu chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~)

Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~ (~1 \le x_i \le 10^8~), là tọa độ văn phòng của ~n~ quốc gia thành viên trên đường thẳng.

~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_k, r_k~ (~1 \le l_k \le r_k \le n~), mô tả yêu cầu họp mặt của các quốc gia từ ~l_k~ đến ~r_k~ vào ngày thứ ~k~.

OUTPUT

Với mỗi truy vấn, in ra tổng khoảng cách nhỏ nhất từ một tọa độ ~X~ đến trụ sở của các quốc gia từ ~l_k~ đến ~r_k~ trên một dòng.

SAMPLE INPUT

5 3
13 26 5 6 7
1 3
2 5
3 4

SAMPLE OUTPUT

21
22
1

SUBTASKS