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.

Tại đất nước Thinkmath, hệ thống giao thông gồm ~N~ thành phố, được đánh số từ ~1~ đến ~N~. Các thành phố được nối với nhau bởi ~N - 1~ con đường hai chiều, sao cho giữa hai thành phố bất kỳ luôn tồn tại đúng một đường đi qua các con đường.

Tại mỗi thành phố có một trạm xử lý xe vận chuyển. Mỗi xe được mô tả bởi một bộ số nguyên ~(X, Y)~. Khi xe đi qua một thành phố, bộ số này sẽ thay đổi tùy theo loại của trạm tại thành phố đó. Mỗi thành phố thuộc một trong hai loại sau:

• Loại A. Nếu xe có thông số hiện tại là ~(X, Y)~, sau khi đi qua thành phố này, thông số trở thành ~(6X + 7Y, 6Y - 7X)~
• Loại B. Nếu xe có thông số hiện tại là ~(X, Y)~, sau khi đi qua thành phố này, thông số trở thành ~(9Y - 6X, 9X + 6Y)~

Ban đầu, loại của mỗi thành phố đã được xác định. Trong ~Q~ ngày tiếp theo, mỗi ngày xảy ra một trong hai sự kiện sau:

• Loại 1. Cho hai thành phố ~U, V~ và một ký tự ~C \in \{A, B\}~. Tất cả thành phố nằm trên đường đi từ thành phố ~U~ đến thành phố ~V~ được biến đổi thành loại ~C~.
• Loại 2. Cho hai thành phố ~U, V~ và thông số ban đầu ~(X, Y)~ của một xe. Một xe vận chuyển có thông số đã cho xuất phát từ thành phố ~U~ và di chuyển đến thành phố ~V~.

Yêu cầu. Với mỗi ngày xảy ra sự kiện loại 2, xác định thông số của xe sau quá trình di chuyển.

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 ~N, Q~ là số thành phố và số ngày xảy ra sự kiện ~(1 \leq N, Q \leq 10^5)~
• Dòng thứ hai chứa một xâu gồm ~N~ ký tự trong tập ~\{A, B\}~. Ký tự thứ ~i \ (1 \leq i \leq N)~ của xâu mô tả loại ban đầu của thành phố ~i~.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~U, V~ mô tả một con đường hai chiều kết nối giữa thành phố ~U~ và thành phố ~V \ (1 \leq U, V \leq N; U\neq V)~
• ~Q~ dòng tiếp theo, dòng thứ ~j \ (1 \leq j \leq Q)~ mô tả sự kiện diễn ra trong ngày thứ ~j~, thuộc hai định dạng sau:
  • Loại 1. 1 U V C ~(1 \leq U, V \leq N; C \in \{A, B\})~.
  • Loại 2. 2 U V X Y ~(1 \leq U ,V\leq N; 0 \leq X,Y \leq 10^9)~

Output

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

• Với mỗi sự kiện loại 2, ghi ra trên một dòng hai số nguyên ~X, Y~ là thông số của xe sau quá trình di chuyển.
• Vì kết quả có thể rất lớn nên hãy in ra phần dư của kết của khi chia cho ~1\,000\,000\,007~.

Subtasks

• Subtask 1 (20% số điểm). ~N, Q \leq 2000~.
• Subtask 2 (30% số điểm). Tồn tại con đường kết nối giữa thành phố ~i~ và thành phố ~i + 1 \ \forall i : 1 \leq i < N~. Các truy vấn loại ~1~ đều có ~U = V~.
• Subtask 3 (30% số điểm). Tồn tại con đường kết nối giữa thành phố ~i~ và thành phố ~i + 1 \ \forall i : 1 \leq i < N~.
• Subtask 4 (20% số điểm). Không có rằng buộc gì thêm.

Sample Input

5 4
AAABB
1 2
1 3
3 4
3 5
2 2 4 1 0
1 1 3 B
2 2 5 1 1
2 4 5 0 1

Sample Output

279 999991535
999989828 12987
1053 702