Năm thứ 69 sau đám tang của dũng sĩ Himmel, Loli cùng tổ đội anh hùng Frieren, Fẻn và Stark sắp hoàn thành mục tiêu cuốc bộ đến Aureole. Trong khi khám phá Dungeon trên đường, ánh mắt của Frieren đã vô tình va vào một cái rương hiếm phát sáng lung linh blink blink. Linh tính mách bảo Frieren rằng trong rương này đang chứa một nùi sách phép ultra rare cấp độ SSS.

Đen một cái là chiếc rương này được khóa bằng hai lớp khóa, hơn nữa còn được bonus thêm một lớp bùa miễn trừ mọi loại sát thương vật lý và sát thương phép. Frieren không chịu buông tha, cổ liền chạy ra cầu xin Loli (vì là người khôn nhất hội =w=) nghĩ cách mở khóa chiếc rương thần. Loli liếc nhìn một lúc thì thấy một đoạn văn dài dán trên thành của rương, đại khái nội dung như sau:

Cho một dãy ~n~ số nguyên dương ~a_i > 1~. Theo định lý của Euclid ta biết được rằng một số nguyên dương luôn có thể phân tích thành tích các thừa số nguyên tố. Một số được gọi là số "khùm đin" nếu như sau khi phân tích số đó ra thành tích các thừa số nguyên tố, số lượng số xuất hiện chẵn lần lớn hơn hẳn số lượng số xuất hiện lẻ lần.

Ví dụ số ~a_i = 67500~. Phân tích ~67500~ thành tích các thừa số nguyên tố ta sẽ có:

~67500 = 2\times 2 \times 3 \times 3\times 3 \times 5\times 5\times 5\times 5~

Ta có thể thấy số ~2~ xuất hiện ~2~ lần, số ~3~ xuất hiện ~3~ lần, số ~5~ xuất hiện ~4~ lần. Vậy có 2 số xuất hiện chẵn lần (~2~ và ~5~), và 1 số xuất hiện lẻ lần (~3~). Do đó ~67500~ là số "khùm đin".

Cuối cùng sẽ có một dãy ~q~ câu hỏi có dạng "~l\ r~", yêu cầu ta tìm số lượng số "khùm đin" có trong dãy con ~(a_l, a_{l+1}, \dots, a_{r})~.

Sau khi định nghĩa số "khùm đin", tờ giấy tiếp tục nói về lớp khóa:

• Mật mã giải khóa thứ nhất là dãy số có ~n~ số, với số thứ ~i~ là 1 nếu ~a_i~ là số "khùm đin", và 0 nếu không phải số "khùm đin".
• Mật mã giải khóa thứ hai là dãy số có ~q~ số, với số thứ ~i~ là đáp án của câu hỏi thứ ~i~.

Vì Loli mải ngắm nhìn Fẻn và Stark bón cơm chó cho nhau nên bạn hãy giúp Loli giải mật mã rương thần nhé =w=

!! Chú ý nhập xuất từ file !!

!! Bài này nhập xuất khá nặng, các em nên dùng thêm cin.tie(0)->sync_with_stdio(0); ở đầu chương trình để không TLE !!

Input

Nhập vào từ file "PSYNUM.INP":

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n\le 5\times 10^5,\ 1\le q\le 10^5)~, lần lượt là độ dài dãy số và số lượng câu hỏi.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(2\le a_i\le 5\times 10^6)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa câu hỏi thứ ~i~ có dạng "~l\ r~".

Output

In ra file "PSYNUM.OUT":

• Dòng đầu tiên chứa ~n~ số là dãy số của mật mã thứ nhất, mỗi số cách nhau một dấu cách.
• ~q~ dòng tiếp theo chứa mật mã thứ hai, dòng thứ ~i~ chứa một số là đáp án của câu hỏi thứ ~i~.

Subtasks

• Subtask 1: ~50\%~ test có ~n \le 1000, q\le 1000~;
• Subtask 2: ~30\%~ test có ~q\le 1000~;
• Subtask 3: ~20\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

5 2
2 3 4 16 5
1 2
2 4

Sample Output 1

0 0 1 1 0 
0
2

Giải thích:

Trong dãy đã cho, ta có số ~4 = 2^2~ và ~16 = 2^4~ là số "khùm đin".

Trong dãy con ~(a_1, a_2)~ không chứa số "khùm đin" nào, nhưng trong dãy con ~(a_2, a_3, a_4)~ lại chứa 2 số "khùm đin".

Nghe thêm nhạc trong khi làm bài để tăng phần hấp dẫn: Link nhạc YouTube

Ta cùng biến căn phòng rộng ~0,01m^2~ thành một ngôi nhà khang trang tiện dụng. Little John sống cực kỳ đạm bạc và chăm chỉ xếp gạch thuê trong hai năm, và dành được nửa triệu Biden để mua một căn nhà ở New York. Tuy nhiên, khi chuyển đến, anh đã bị sốc vì nó quá nhỏ. Anh thậm chí còn không thể duỗi ngón tay ra. Bây giờ, hãy tìm cách chúng ta có thể giúp Little John biến nó thành một ngôi nhà tiện dụng. Đầu tiên, chúng ta sẽ xây dựng một khung bền hình tam giác bằng thép vuông mạ kẽm chống gỉ (galvanized square steel) được neo chắc chắn vào tường chứa đầy các thanh thép lưới và bê tông bằng vít giãn nở mượn từ người dì, để ngôi nhà có độ bền đến ~10000~ năm sau cũng chưa hỏng.

Mà trước hết ta cần mua thép vuông mạ kẽm chống gỉ để làm khung đã. Little John té lẹ đến một cửa hàng có bày bán ~n~ thanh thép (vuông mạ kẽm chống gỉ), thanh thép thứ ~i~ có độ dài là ~a_i~.

Bạn cần đếm số lượng cách chọn bộ ba ~(i,j,k)\ (1 \le i < j < k \le n)~ sao cho ba thanh thép đã chọn có độ dài lần lượt là ~a_i, a_j~ và ~a_k~ sẽ tạo thành một khung hình tam giác.

!! Chú ý nhập xuất từ file !!

Input

Nhập vào từ file "TRISTEEL.INP":

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1 \le n\le 8000)~ là số lượng thanh thép vuông mạ kẽm chống gỉ.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1\le a_i\le 10^5)~ là độ dài của các thanh thép.

Output

In ra file "TRISTEEL.OUT":

• In ra một số nguyên duy nhất là số lượng cách chọn bộ ba ~(i, j, k)~ thỏa mãn điều kiện đề bài.

Subtasks

• Subtask 1: ~40\%~ test có ~n \le 500~;
• Subtask 2: ~30\%~ test có ~n \le 3000~;
• Subtask 3: ~30\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

3

Giải thích:

• Những bộ ba thỏa mãn đề bài lần lượt là ~(2,3,4), (2,4,5)~ và ~(3,4,5)~.

Để tích lũy đầu cơ hàng trong mùa dịch COVID, Loli đang cần mua hai loại mặt hàng ~A~ và ~B~ cùng nhau. Qua tìm hiểu trên mạng, Loli đã lập được danh sách gồm ~n~ mặt hàng loại ~A~ (đánh số từ ~1~ đến ~n~, mặt hàng thứ ~i~ có giá là ~A_i~) và ~n~ mặt hàng loại ~B~ (đánh số từ ~1~ đến ~n~, mặt hàng thứ ~i~ có giá là ~B_i~).

Nếu Loli chọn mua mặt hàng loại ~A~ thứ ~i~ và mặt hàng loại ~B~ thứ ~j~ thì Loli sẽ phải trả số tiền là ~A_i+B_j~.

Loli thực sự rất muốn biết trong ~n^2~ sự lựa chọn có thể của mình, nếu đem số tiền phải trả trong các sự lựa chọn đó sắp xếp không giảm thì ~k~ sự lựa chọn đầu tiên sẽ có số tiền lần lượt như thế nào.

Yêu cầu: Cho biết ~n,k~ và hai dãy số nguyên dương ~A_1,A_2,\dots ,A_n~, ~B_1,B_2,\dots ,B_n~. Hãy in ra dãy ~k~ số (không giảm) là tổng số tiền phải trả của mỗi lựa chọn trong ~k~ sự lựa chọn đầu tiên.

!! Chú ý nhập xuất từ file !!

Input

Nhập vào từ file "KCHOOSE.INP":

• Dòng đầu tiên gồm hai số nguyên ~n,k\ (1\le n,k\le 10^5;\ k\le n^2)~;
• Dòng thứ hai gồm một dãy ~n~ số nguyên dương ~A_1,A_2,\dots ,A_n\ (1\le A_i\le 10^9)~;
• Dòng thứ ba gồm một dãy ~n~ số nguyên dương ~B_1,B_2,\dots ,B_n\ (1\le B_i\le 10^9)~.

Output

In ra file "KCHOOSE.OUT":

• Một dòng gồm ~k~ số nguyên là đáp số bài toán.

Subtasks

• Subtask 1: ~60\%~ test có ~n \le 1000~;
• Subtask 2: ~40\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 4
5 1 2
2 6 4

Sample Output 1

3 4 5 6

Giải thích:

Có ~9 = 3\times 3~ sự lựa chọn với số tiền (sau khi sắp xếp không giảm) là: ~3, 4, 5, 6, 7, 7, 8, 9, 11~.

Trong đó ~4~ sự lựa chọn đầu tiên là: ~3, 4, 5, 6~.

Loli là một lập trình viên có tiếng. Cô ấy đã cho ra đời một trình soạn thảo cực xịn xò. Tuy nhiên kỳ lạ là trình soạn thảo này chỉ làm việc với các số nguyên??

Ta có một con trỏ lệnh. Ban đầu trình soạn thảo không có số nào, dãy số hiện tại là rỗng. Loli thực hiện lần lượt ~q~ thao tác thuộc các dạng sau:

• ~I\ x~: Chèn số ~x~ ~(|x| \le 1000)~ vào ngay trước con trỏ lệnh.
• ~D~: Xoá số ngay trước con trỏ lệnh (hoặc không làm gì nếu con trỏ đã ở đầu dãy).
• ~L~: Di chuyển con trỏ lệnh sang trái một đơn vị (hoặc không làm gì nếu con trỏ đã ở đầu dãy).
• ~R~: Di chuyển con trỏ lệnh sang phải một đơn vị (hoặc không làm gì nếu con trỏ đã ở cuối dãy).

Bên trên đều là những lệnh bình thường của một trình soạn thảo. Tuy nhiên tính năng đặc biệt của trình soạn thảo nằm ở thao tác đặc biệt có dạng:

• ~Q\ k~: Giả sử dãy đứng trước con trỏ đánh số từ ~1~ tới ~n~ tính từ bên trái là ~a_1,a_2,...,a_n~, ta cần tính và in ra ~X = max(S_1, S_2, \dots, S_k)~, với ~S_i = a_1 + a_2 + ... + a_i~.

Yêu cầu:

• Thực hiện lần lượt ~q~ thao tác cho trước; với thao tác loại ~Q\ k~, cần tính và in ra ~X~.
• Sau khi thực hiện ~q~ thao tác, in ra dãy số cuối cùng của trình soạn thảo.

!! Chú ý nhập xuất từ file !!

Input

Nhập vào từ file "EDITOR.INP":

• Dòng đầu chứa số nguyên dương ~q~ ~(1\le q\le 5 \times 10^5)~ là số lượng thao tác.
• ~q~ dòng tiếp theo, mỗi dòng chứa một thao tác, theo dạng đã nói ở trên.
• Dữ liệu đảm bảo với các thao tác dạng ~Q\ k~ thì đã có ít nhất một số đứng trước con trỏ lệnh và ~k~ không quá số lượng số đứng trước con trỏ lệnh.

Output

In ra file "EDITOR.OUT":

• Với mỗi truy vấn dạng ~Q\ k~, in ra kết quả trên một dòng.
• Dòng cuối cùng in ra dãy số của trình soạn thảo sau khi thực hiện xong ~q~ thao tác.

Subtasks

• Subtask 1: ~50\%~ test có ~q\le 10^3~ và không có thao tác loại ~Q\ k~;
• Subtask 2: ~20\%~ test có ~q\le 10^3~;
• Subtask 3: ~30\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

9
I 2
I -1
I 4
Q 3
L
D
I 5
R
Q 1

Sample Output 1

5
2
2 5 4

Giải thích:

Ban đầu ta có dãy số rỗng ~[]~, con trỏ ta tạm đánh dấu là ~|~ (chú ý tới ký hiệu con trỏ):

• Ba thao tác đầu là thao tác ~I~, sau khi thực hiện ta có ~[2\ -1\ 4|]~
• Thực hiện thao tác ~Q\ 3~, ta có ~S_1 = 2, S_2 = 1, S_3=5~. Vậy giá trị lớn nhất là ~X=5~.
• Thực hiện thao tác ~L~, ta có ~[2\ -1|\ 4]~.
• Thực hiện thao tác ~D~, ta xóa ~-1~, còn lại ~[2|\ 4]~.
• Thực hiện thao tác ~I\ 5~, ta có ~[2\ 5|\ 4]~.
• Thực hiện thao tác ~R~, ta có ~[2\ 5\ 4|]~
• Thực hiện thao tác ~Q\ 1~, ta có ~S_1 = 2~. Vậy giá trị lớn nhất là ~X=2~.
• Cuối cùng, in ra dãy số hiện tại, đó là ~[2\ 5\ 4]~.