Cho ~T~ câu hỏi và số nguyên dương ~k~. Mỗi câu hỏi được mô tả bởi một số nguyên dương ~n~. Với mỗi câu hỏi, bạn cần đếm số bộ có thứ tự ~(a, b_1, b_2, \ldots, b_k)~ thỏa mãn đồng thời các điều kiện sau:

• ~1 \leq a, b_1, b_2, \ldots, b_k \leq n~;
• ~b_1, b_2, \ldots, b_k~ là ước của ~a~;
• Ước chung lớn nhất của các số ~b_1, b_2, \ldots, b_k~ là ~1~.

Nhắc lại.

• Một số nguyên dương ~b_i \ (1 \leq i \leq k)~ được gọi là ước của ~a~ nếu tồn tại một số nguyên dương ~d~ sao cho ~a = d\cdot b_i~
• Ước chung lớn nhất của các số ~b_1, b_2, \ldots, b_k~ là số nguyên dương ~m~ lớn nhất đồng thời là ước của ~b_1, b_2, \ldots, b_k~

Yêu cầu. Tính đáp án cho mỗi câu hỏi.

Input

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Dòng đầu tiên chứa hai số nguyên dương ~T~ và ~k~ lần lượt là số câu hỏi và số lượng các số ~b_i~ được chọn trong mỗi bộ ~(T \leq 10^5; k \leq 10^9)~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ mô tả một câu hỏi ~(n \leq 10^5)~

Output

Ghi ra luồng nhập/xuất chuẩn gồm:

• ~T~ dòng, mỗi dòng chứa đáp án của câu hỏi tương ứng khi chia dư cho ~998\,244\,353~.

Subtasks

• Subtask 1 (15% số điểm). ~k = 2; n \leq 100~.
• Subtask 2 (35% số điểm). ~k = 2~.
• Subtask 3 (50% số điểm). Không có rằng buộc gì thêm.

Sample Input

3 2
3
6
7

Sample Output

7
24
27

Giải thích

Trong câu hỏi đầu tiên, các bộ ~(a, b_1, b_2)~ thỏa mãn là:

• ~(1, 1, 1)~
• ~(2, 1, 1)~
• ~(2, 1, 2)~
• ~(2, 2, 1)~
• ~(3, 1, 1)~
• ~(3, 1, 3)~
• ~(3, 3, 1)~

Một xưởng mộc đang chuẩn bị các bộ gỗ để lắp ráp. Trên bàn gia công có ~N~ khúc gỗ rời nhau được xếp thành một hàng từ trái sang phải, đánh số lần lượt từ ~1~ đến ~N~. Khúc gỗ thứ ~i \ (1 \leq i \leq N)~ có độ dài ~L_i~. Người thợ muốn dán các khúc gỗ này lại thành một số đoạn gỗ lớn. Mỗi đoạn gỗ lớn phải được tạo thành từ một hoặc nhiều khúc gỗ liên tiếp trong hàng ban đầu, và mỗi khúc gỗ ban đầu phải thuộc đúng một đoạn gỗ lớn.

Khi một đoạn gỗ lớn được tạo từ các khúc gỗ ở vị trí ~l, l + 1, \ldots, r \ (1 \leq l \leq r \leq N)~, các khúc gỗ trong đoạn đó sẽ được xét lại theo thứ tự từ trái sang phải. Khi đó, khúc gỗ ban đầu ở vị trí ~i \ (l \leq i \leq r)~ sẽ có vị trí mới trong đoạn gỗ lớn là ~i - l + 1~.

Theo tiêu chuẩn của xưởng, một khúc gỗ được xem là đạt chuẩn nếu độ dài của nó đúng bằng vị trí mới của nó trong đoạn gỗ lớn. Ngược lại, nếu ~a_i \neq i - l + 1~, khúc gỗ đó được xem là bị lệch chuẩn. Để đánh giá những phương án dán các khúc gỗ, các chuyên gia trong xưởng mộc định nghĩa độ lệch của một đoạn gỗ lớn là số khúc gỗ bị lệch chuẩn trong đoạn đó. Người thợ muốn chia hàng khúc gỗ ban đầu thành các đoạn liên tiếp rồi dán lại sao cho tổng độ lệch của tất cả các đoạn gỗ lớn là nhỏ nhất.

Yêu cầu. Hãy xác định tổng độ lệch nhỏ nhất có thể đạt được.

Input

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Dòng đầu tiên chứa một số nguyên dương ~N~ là số lượng khúc gỗ ~(1 \leq N \leq 2\cdot 10^5)~
• Dòng thứ hai chứa ~N~ số nguyên ~L_1, L_2, \ldots, L_N~ là độ dài của các khúc gỗ ~(1 \leq L_i \leq N)~

Output

Ghi ra luồng nhập/xuất chuẩn gồm:

• Dòng đầu tiên chứa một số nguyên là độ lệch nhỏ nhất có thể đạt được.
• Dòng thứ hai chứa một số nguyên ~K~ là số đoạn gỗ lớn trong phương án dán gỗ được chọn.
• Trong ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~, mô tả một đoạn gỗ lớn được tạo từ các khúc gỗ liên tiếp có chỉ số từ ~l~ đến ~r~. Các đoạn gỗ phải được liệt kê theo thứ tự tăng dần của ~l~.

Nếu có nhiều phương án dán gỗ đạt tổng độ lệch nhỏ nhất, thí sinh có thể in ra một phương án bất kỳ.

Subtasks

• Subtask 1 (25% số điểm). ~N \leq 200~.
• Subtask 2 (25% số điểm). ~N \leq 3000~.
• Subtask 3 (25% số điểm). ~L_i \leq 200~ với mọi ~i~ sao cho ~1 \leq i \leq N~.
• Subtask 4 (25% số điểm). Không có rằng buộc gì thêm.

Sample Input

8
1 2 4 1 2 9 1 3

Sample Output

3
3
1 3
4 5
6 8

Giải thích

Ta có thể chia dãy khúc gỗ thành các nhóm: ~[1, 2, 4], [1, 2], [9, 1, 3]~. Độ lệch của các nhóm lần lượt là ~1, 0, 2~, vì thế tổng độ lệch là ~1 + 0 + 2 = 3~.

Đây là bài tương tác (interactive)

Sau khi các bạn học sinh THCS hoàn thành kỳ thi tuyển sinh vào lớp 10, cô giáo muốn tổ chức một buổi sinh hoạt nhẹ nhàng cho câu lạc bộ Tin học. Thay vì cho các bạn làm ngay những bài toán quen thuộc, cô giáo quyết định giới thiệu trước một vài dạng bài đặc biệt mà các bạn có thể gặp khi học tập môn Tin học ở cấp 3. Trong số đó có những dạng bài khác với truyền thống như bài tương tác (interactive), bài giao tiếp hai chiều (communication) hay bài chỉ cần nộp kết quả (output-only). Cô giáo đặc biệt yêu thích dạng bài tương tác, vì ở dạng bài này, người làm bài không chỉ viết chương trình để tính ra đáp án, mà còn phải biết cách đặt câu hỏi thật khéo để tìm được thông tin cần thiết.

Để các bạn dễ hình dung hơn, cô giáo nghĩ ra một trò chơi nhỏ. Cô chuẩn bị một dãy gồm ~N~ viên bi được xếp liên tiếp trên một hàng, các viên bi được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải. Trong dãy có ~X~ viên bi màu đỏ và ~Y~ viên bi màu xanh, với ~X, Y~ là các số nguyên dương thỏa mãn ~X + Y = N~. Ban đầu, dãy bi được xếp rất gọn gàng theo quy tắc: ~X~ viên bi màu đỏ đứng trước, sau đó là ~Y~ viên bi màu xanh.

Ví dụ, nếu ~N = 5, X = 3~ và ~Y = 2~, thì dãy bi ban đầu là:

~[R, R, R, B, B]~

trong đó ~R~ biểu thị một viên bi màu đỏ, còn ~B~ biểu thị một viên bi màu xanh.

Trước khi cho học sinh đặt câu hỏi, cô giáo bí mật chọn hai chỉ số ~L~ và ~R~ với ~1 \leq L < R \leq N~, rồi đảo ngược thứ tự các viên bi từ vị trí ~L~ đến vị trí ~R~. Đoạn được chọn phải chứa cả bi màu đỏ và bi màu xanh, vì cô giáo không muốn chọn một đoạn mà sau khi đảo xong dãy bi không thay đổi gì.

Ví dụ, với dãy bi ban đầu ~[R, R, R, B, B]~:

• Nếu cô giáo chọn ~L = 2~ và ~R = 4~, sau khi đảo ngược đoạn từ vị trí ~2~ đến vị trí ~4~, dãy bi trở thành

~[R, B, R, R, B]~

• Nếu cô giáo chọn ~L = 1~ và ~R = 5~, sau khi đảo ngược đoạn từ vị trí ~1~ đến vị trí ~5~, dãy bi trở thành

~[B, B, R, R, R]~

• Cô giáo không thể chọn ~L = 1~ và ~R = 3~ vì đoạn từ vị trí ~1~ đến vị trí ~3~ là ~[R, R, R]~, chỉ chứa các viên bi màu đỏ.

Sau khi thực hiện xong phép đảo ngược, cô giáo bắt đầu cho các bạn đặt câu hỏi. Các bạn chỉ biết số ~N~, tức là số lượng viên bi trong dãy. Các bạn không biết dãy bi ban đầu có bao nhiêu viên bi màu đỏ, bao nhiêu viên bi màu xanh, cũng không biết các chỉ số ~L, R~ mà cô giáo sử dụng để đảo dãy bi.

Mỗi câu hỏi mà các bạn học sinh được phép đặt ra có dạng:

Trong các viên bi từ vị trí ~i~ đến vị trí ~j~, có bao nhiêu viên bi màu đỏ?

với ~1 \leq i \leq j \leq N~.

Với mỗi câu hỏi, cô giáo sẽ trả lời chính xác số viên bi đỏ trong đoạn đó.

Ví dụ, sau khi cô giáo thực hiện phép đảo ngược, dãy bi thu được là ~[R, B, R, R, B]~. Khi đó:

• Nếu học sinh đặt câu hỏi với ~i = 2~ và ~j = 3~, cô giáo sẽ xét đoạn từ vị trí ~2~ đến vị trí ~3~, tức là đoạn ~[B, R]~. Đoạn này có ~1~ viên bi màu đỏ, nên câu trả lời của cô giáo là ~1~.

• Nếu học sinh đặt câu hỏi với ~i = 1~ và ~j = 4~, cô giáo sẽ xét đoạn từ vị trí ~1~ đến vị trí ~4~, tức là đoạn ~[R, B, R, R]~. Đoạn này có ~3~ viên bi màu đỏ, nên câu trả lời của cô giáo là ~3~.

• Các học sinh không thể sử dụng các cặp ~(i, j)~ là ~(3, 2), (0, 3)~ hoặc ~(6, 7)~ để đặt câu hỏi vì các cặp này đều vi phạm điều kiện ~1 \leq i \leq j \leq N~.

Nhiệm vụ của các bạn học sinh là tìm ra hai chỉ số ~L~ và ~R~ mà cô giáo đã bí mật chọn ban đầu.

Việt là lớp trưởng của lớp và cũng là bạn rất thích những bài toán mới lạ. Thấy cả lớp còn bối rối vì chưa quen với dạng bài tương tác, Việt quyết định đứng ra tìm cách giải trò chơi này. Tuy nhiên, dãy bi mà cô giáo chuẩn bị có thể rất dài, nên Việt muốn tìm được hai chỉ số ~L~ và ~R~ bằng càng ít câu hỏi càng tốt.

Yêu cầu. Hãy giúp Việt thực hiện trò chơi của cô giáo.

Tương tác

Lưu ý rằng quá trình tương tác được thực hiện thông qua luồng dữ liệu chuẩn stdin và stdout.

Đầu tiên, chương trình của thí sinh đọc vào hai số nguyên dương ~T \ (T \leq 20)~ và ~\phi \ (\phi \leq 2)~, lần lượt là số lượng trường hợp thử nghiệm và số hiệu của subtask.

Với mỗi trường hợp thử nghiệm, quy trình tương tác diễn ra như sau.

• Trước hết, chương trình đọc vào một số nguyên ~N \ (2 \leq N \leq 10^9)~, là số viên bi trong dãy.

• Để đặt câu hỏi về số viên bi đỏ trong đoạn từ vị trí ~i~ đến vị trí ~j~, chương trình của thí sinh in ra luồng dữ liệu chuẩn một dòng theo dạng: ? i j, trong đó ~1 \leq i \leq j \leq N~. Sau đó, chương trình đọc từ luồng dữ liệu chuẩn một số nguyên, là câu trả lời của cô giáo.

• Khi đã xác định được hai chỉ số ~L~ và ~R~ mà cô giáo đã chọn để thay đổi dãy bi ban đầu, chương trình của thí sinh in ra luồng dữ liệu chuẩn một dòng theo dạng: ! L R.

Sau khi in một lệnh, đừng quên in dấu xuống dòng và flush đầu ra chuẩn. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;
• sys.stdout.flush() trong Python.

Thí sinh có thể tham khảo chương trình minh họa quy trình tương tác trong phần Giải thích.

Hệ thống chấm của bài này là không thích ứng (non-adaptive). Điều đó có nghĩa là dãy bi ban đầu cũng như hai chỉ số ~L~ và ~R~ đã được cố định trước khi chương trình của thí sinh bắt đầu đặt câu hỏi.

Chấm điểm

Với mỗi test, nếu chương trình của thí sinh mắc một trong các lỗi sau, phần trăm số điểm nhận được cho test đó là ~0\%~:

• bộ chỉ số ~(i, j)~ khi đặt câu hỏi không hợp lệ;
• hai chỉ số ~L~ và ~R~ được đưa ra không khớp với hai chỉ số cô giáo đã chọn ban đầu;
• thực hiện quy trình tương tác sai quy cách;
• chương trình chạy quá thời gian, chạy quá bộ nhớ, dịch lỗi, hoặc kết thúc bất thường.

Ngược lại, gọi ~Q~ là số câu hỏi lớn nhất mà chương trình sử dụng trong các trường hợp thử nghiệm của test đó. Phần trăm số điểm nhận được cho test được tính như sau:

• Nếu ~Q > 267~, thí sinh nhận được ~0\%~ số điểm của test.
• Nếu ~67 < Q \leq 267~, phần trăm điểm thí sinh nhận được là

~100\% \times \left(\frac{268 - Q}{201}\right)^2~

• Nếu ~Q \leq 67~, thí sinh nhận được ~100\%~ số điểm của test.

Subtasks

• Subtask 1 (20% số điểm). ~\phi = 1~ và ~N \leq 267~.
• Subtask 2 (80% số điểm). ~\phi = 2~.

Sample Input

2 1
3

1

0

0

5

3

1

1

2

Sample Output

? 1 3

? 1 1

? 1 2

! 1 3

? 1 5

? 1 2

? 1 1

? 1 3

! 2 4

Giải thích

Test ví dụ là một test thuộc subtask 1.

• Tại trường hợp thử nghiệm thứ nhất, dãy bi ban đầu là ~[R, B, B]~. Cô giáo chọn ~L = 1~ và ~R = 3~ sau đó thu được dãy ~[B, B, R]~.
• Tại trường hợp thử nghiệm thứ hai, dãy bi ban đầu là ~[R, R, R, B, B]~. Cô giáo chọn ~L = 2~ và ~R = 4~ sau đó thu được dãy ~[R, B, R, R, B]~.

Thí sinh có thể xem chương trình minh họa quy trình tương tác của test ví dụ ở liên kết các sau:

• Phiên bản dành cho ngôn ngữ lập trình C++ tại đây.
• Phiên bản dành cho ngôn ngữ lập trình Python tại đây.

Đội tuyển lập trình của trường đang chuẩn bị cho kỳ thi ICPC sắp tới. Để giúp các thành viên làm quen với áp lực thời gian và rèn luyện chiến thuật chọn thứ tự giải bài, huấn luyện viên tổ chức một buổi luyện tập theo thể thức gần giống một cuộc thi lập trình thực tế.

Trong buổi luyện tập này có ~N~ bài toán, được đánh số từ ~1~ đến ~N~. Buổi luyện tập bắt đầu tại thời điểm ~0~. Với mỗi bài toán thứ ~i \ (1 \leq i \leq N)~, điểm phạt của bài đó không cố định mà tăng dần theo thời gian: cứ mỗi phút trôi qua kể từ lúc bắt đầu buổi luyện tập, điểm phạt của bài ~i~ tăng thêm ~A_i~. Nếu một đội hoàn thành bài ~i~ tại thời điểm ~T~, đội đó sẽ bị cộng thêm ~A_i \cdot T~ điểm phạt cho bài này.

Trong bảng xếp hạng của buổi luyện tập, tiêu chí đầu tiên là số lượng bài hoàn thành. Đội nào hoàn thành được nhiều bài hơn sẽ có thứ hạng cao hơn. Nếu hai đội hoàn thành cùng số lượng bài, đội có tổng điểm phạt nhỏ hơn sẽ được xếp trên. Vì vậy, khi một đội chắc chắn có thể giải hết tất cả các bài, thứ tự làm bài trở thành yếu tố rất quan trọng để tối thiểu hóa tổng điểm phạt.

Huấn luyện viên nhận thấy rằng trong các kỳ thi ICPC thật, không phải lúc nào các đội cũng được tự do chọn bài một cách hoàn toàn. Có những tình huống một bài toán nên được giải trước một bài toán khác, chẳng hạn vì bài sau cần ý tưởng từ bài trước, hoặc vì huấn luyện viên muốn kiểm tra khả năng tuân thủ một chiến thuật nhất định. Do đó, huấn luyện viên chuẩn bị ~M~ thẻ thử thách. Mỗi thẻ ghi hai số nguyên dương phân biệt ~X~ và ~Y~. Nếu một đội bốc phải thẻ này, đội đó bắt buộc phải hoàn thành bài ~X~ trước bài ~Y~.

Bạn là một thành viên rất giỏi của đội tuyển, và bạn chắc chắn có thể hoàn thành toàn bộ n bài toán trong buổi luyện tập. Bài toán thứ ~i~ cần đúng ~B_i~ phút để giải xong, bất kể nó được làm ở thời điểm nào. Trước mỗi lượt luyện tập, bạn có thể bốc phải một trong các thẻ thử thách mà huấn luyện viên đã chuẩn bị. Với mỗi thẻ, bạn cần chọn một thứ tự làm tất cả các bài sao cho điều kiện trên thẻ được thỏa mãn, đồng thời tổng điểm phạt sau khi hoàn thành toàn bộ ~N~ bài toán là nhỏ nhất có thể.

Yêu cầu. Với mỗi thẻ thử thách thứ ~j \ (1 \leq j \leq M)~ hãy tính tổng điểm phạt nhỏ nhất có thể đạt được nếu bạn bốc phải thẻ đó.

Input

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Dòng đầu tiên chứa một số nguyên dương ~N, M~ là số lượng bài toán và số thẻ thử thách ~(2 \leq N \leq 10^5; 1 \leq M \leq 10^5)~
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ là hệ số điểm phạt của các bài ~(1 \leq A_i \leq 1000)~
• Dòng thứ ba chứa ~N~ số nguyên dương ~B_1, B_2, \ldots, B_N~ là thời gian cần để giải mỗi bài ~(1 \leq B_i \leq 1000)~
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương phân biệt ~X, Y~ ứng với một thẻ thử thách ~(1 \leq X, Y \leq N)~

Output

Ghi ra luồng nhập/xuất chuẩn gồm:

• ~M~ dòng, dòng thứ ~j \ (1 \leq j \leq M)~ chứa một số nguyên là tổng điểm phạt nhỏ nhất có thể đạt được nếu bạn bốc phải thẻ thử thách thứ ~j~.

Subtasks

• Subtask 1 (20% số điểm). ~N,M \leq 10~.
• Subtask 2 (30% số điểm). ~N,M \leq 100~.
• Subtask 3 (30% số điểm). ~N,M \leq 5000~.
• Subtask 4 (20% số điểm). Không có rằng buộc gì thêm.

Sample Input

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

Sample Output

44
45
52
52
47

Giải thích

Thứ tự làm bài tối ưu cho mỗi thẻ thử thách là như sau:

• Thẻ ~1~; ~(4, 2, 3, 1)~
• Thẻ ~2~; ~(4, 3, 2, 1)~
• Thẻ ~3~; ~(2, 3, 1, 4)~
• Thẻ ~4~; ~(4, 3, 1, 2)~
• Thẻ ~5~; ~(3, 4, 2, 1)~ hoặc ~(2, 3, 4, 1)~