Uesugi Tèo - một coder nổi tiếng trong đội tuyển Tin Ams, đã được gia đình nhà Nakano giàu có thuê làm gia sư Tin học dạy kèm con họ. Lạ thay, những đứa con của gia đình nọ là những người chị em sinh năm học cùng khối với cậu trên trường. Bằng quyết tâm và nhiệt huyết với việc giúp 5 chị em họ vượt qua bài kiểm tra của thầy Tùng, Uesugi đã giao mỗi người một bài toán phù hợp với năng lực của họ, với phần thưởng đi kèm là một chuyến dã ngoại cùng cậu. Sau khi đắn đo suy nghĩ, cậu giao cho Nino Nakano bài toán như sau:

Nino được cho ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ và một số nguyên dương ~K~. Cô được yêu cầu chọn ra một dãy các vị trí ~i_1, i_2, \dots, i_M \ (1 \leq M \leq N)~ trong số ~N~ vị trí ban đầu, sao cho trong những vị trí được chọn, không tồn tại hai vị trí ~i_x, i_y \ (i_x \neq i_y) ~ thỏa mãn ~a_{i_x} \times a_{i_y}~ là một lũy thừa bậc ~K~. Ví dụ, với ~K = 2~ và ~a = \{1, 2, 8, 16, 3, 9\}~, Nino có thể chọn tập ~\{1, 2, 5\}~ hoặc ~\{4\}~, nhưng không thể chọn đồng thời vị trí ~(1, 4)~, hay ~(4, 6)~. Để làm bài toán khó hơn, Uesugi yêu cầu Nino tìm dãy con lớn nhất thỏa mãn điều kiện trên. Nếu không tồn tại đoạn thỏa mãn, Nino cần trả về -1.

Nino không muốn trông cậy vào sự giúp đỡ của Uesugi, nên bạn được yêu cầu giải bài toán này nhanh nhất có thể để không làm phật lòng Uesugi cũng như những người chị em của cô.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương ~N, K \ (1 \leq N \leq 2 \times 10^5, \ 2 \leq K \leq 5)~.
• Dòng tiếp theo nhập vào ~N~ số nguyên dương ~a_1, a_2, \dots, a_N \ (1 \leq a_i \leq 2 \times 10^6)~ được ngăn bởi dấu cách.

Output

• In ra một số nguyên duy nhất là kết quả của bài toán hoặc -1 nếu không tồn tại dãy thỏa mãn.

Scoring

• Subtask 1 ~(7p)~: ~N \leq 14~.
• Subtask 2 ~(13p)~: ~N \leq 20~.
• Subtask 3 ~(11p)~: ~K = 2, \ N \leq 2000~.
• Subtask 4 ~(16p)~: ~N \leq 2000~.
• Subtask 5 ~(22p)~: ~K = 2~.
• Subtask 6 ~(31p)~: Không có ràng buộc gì thêm.

Sample Input 1

6 2
1 2 8 16 3 9

Sample Ouput 1

3

Notes

• Chọn các số ~\{1, 3, 5\}~.

Sương mây mịt mùng

Núi sông điệp trùng

Chân không chịu dừng

Leo, leo đèo

Vào ngày cuối cùng của kì nghỉ hè, 4 cô gái đến từ Shimokitazawa quyết định đi chơi có thêm thật nhiều kỉ niệm đẹp. Họ ghé thăm những quán ăn, bờ biển, và cuối cùng đặt chân đến một đài quan sát cao chót vót, buộc họ phải leo thang lên từ mặt đất. Kita - người hướng ngoại nhất nhóm - rất muốn cả nhóm cùng leo lên những bậc thang đó, nhưng ba người còn lại là Bocchi, Ryo và Nijika cảm thấy quá mệt mỏi và tìm cách khác để tận hưởng việc leo thang. May thay, họ có thể sử dụng thang cuốn ở gần đó để thay thế. Trên đường lên thang cuốn, Bocchi bỗng nhận thấy những tính chất rất đặc biệt của những bậc thang trước mắt, chúng có hình thù giống như những ngọn đồi trùng điệp. Từ quan sát thú vị đó, Bocchi nảy ra bài toán sau:

Bocchi giả sử độ cao của những bậc thang cô thấy là một mảng ~N~ phần tử ~a_1, a_2, \dots, a_N \ (-10^9 \leq a_i \leq 10^9)~ (thường xuyên sống trong bóng tối khiến Bocchi tưởng tượng bậc thang có độ cao âm). Bocchi gọi một dãy ~l, r~, với ~1 \leq l \leq r \leq N~ là dãy "đồi núi" nếu ~a_l = a_r~ và với mọi ~l \leq i \leq r~, ta có ~a_l \geq a_i~. Điều này cũng đồng nghĩa dãy ~l = r~ cũng là một dãy "đồi núi". Bocchi quy ước độ đẹp của một dãy "đồi núi" là ~r - l~.

Do đang di chuyển trên thang cuốn, mỗi lần quan sát của Bocchi không cố định. Cụ thể, Bocchi có tổng cộng ~Q~ lần quan sát. Ở lần thứ ~i~, cô nhìn thấy các số trong khoảng ~[L_i, R_i] \ (1 \leq L_i \leq R_i \leq N)~. Trong mỗi lần quan sát, Bocchi muốn biết độ dài của dãy "đồi núi" dài nhất nằm trong tầm nhìn của cô. Nói cách khác, với mỗi ~[L_i, R_i]~, Bocchi muốn tìm dãy "đồi núi" ~[x, y]~ có độ đẹp lớn nhất thỏa mãn ~L_i \leq x \leq y \leq R_i~. Dễ thấy luôn tồn tại đáp án thỏa mãn.

Do mắc chứng sợ giao tiếp xã hội nặng, Bocchi có thể bất chợt nổ tung hoặc tan chảy nếu bị buộc phải giao tiếp với người khác. Nên cô đã chuyển lời cho Nijika, và giờ là bạn. Hãy giúp Bocchi nhé!

Input

• Dòng đầu chứa hai số nguyên dương ~N, Q \ (1 \leq N, Q \leq 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N \ (-10^9 \leq a_i \leq 10^9)~ được ngăn bởi dấu cách.
• Q dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i, R_i \ (1 \leq L_i \leq R_i \leq N)~ biểu thị lần quan sát thứ ~i~ của Bocchi.

Output

• In ra ~Q~ dòng, với dòng thứ ~i~ là kết quả cho lần quan sát thứ ~i~ của Bocchi.

Scoring

• Subtask 1 ~(14p)~: ~N, Q \leq 300~.
• Subtask 2 ~(17p)~: ~N \leq 5000~.
• Subtask 3 ~(13p)~: ~L_i = 1~ với mọi ~1 \leq i \leq Q~.
• Subtask 4 ~(15p)~: ~L_1 \leq R_1 < L_2 \leq R_2 < L_3 \leq ... \leq R_{Q - 1} < L_Q \leq R_Q~.
• Subtask 5 ~(17p)~: ~a_i \in \{0, 1\}~ với mọi ~1 \leq i \leq N~.
• Subtask 6 ~(24p)~: Không có ràng buộc gì thêm.

Sample Input 1

10 10
6 4 10 10 10 3 4 5 4 3
4 10
3 8
3 5
1 10
2 3
4 6
1 2
2 6
9 10
5 7

Sample Output 1

1
2
2
2
0
1
0
2
0
0

Notes

• Ở lần quan sát đầu tiên, Bocchi có thể chọn đoạn ~[4, 5]~.
• Ở lần quan sát thứ hai, Bocchi có thể chọn đoạn ~[3, 5]~.

Sample Input 2

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

Sample Output 2

2
0
2
0
4

Notes

• Các đoạn có thể chọn trong các truy vấn là ~(1, 3), (2, 2), (3, 5), (5, 5), (1, 5)~.

Don't play HSR! But Firefly so cute :3

MACKSAY đang trên đường khai phá cùng đội tàu Astral. Họ vừa đến Xianzhou Luofu thì Feixiao và Jing Yuan đã giao cho họ một nhiệm vụ rất khó, đó là tính toán tất cả sức mạnh giữa các Mỏ neo không gian.

Các Mỏ neo hình thành một đồ thị dạng cây ~N~ đỉnh, với ~N - 1~ đường đi. Đường đi nối giữa hai Mỏ neo ~u_i~ và ~v_i~ có khoảng cách là ~d_i~. Mỗi Mỏ neo ~i~ có một chỉ số gọi là sức mạnh không gian ~A_i~. Sức mạnh của đường đi giữa hai mỏ neo ~u~ và ~v~ được tính bằng công thức ~f(u,v) = s(u,v) \times dist(u,v)~, trong đó ~s(u,v)~ là tổng các ước chung của ~A_u~ và ~A_v~ và ~dist(u,v)~ là độ dài đường đi ngắn nhất giữa ~u~ và ~v~.

Tướng quân Feixiao và Jing Yuan muốn các bạn tính tổng của ~f(i,j)~ với mọi ~1 \leq i < j \leq N~.

MACKSAY ngay lập tức gọi Firefly (người yêu của anh!) đến ứng cứu. Và Firefly, tất nhiên với trí thông minh và sự xinh đẹp của mình, đã giải xong bài toán trong ~0.2~ giây! Vậy còn các bạn, liệu các bạn có giải được bài toán này?

Input

• Dòng đầu chứa số nguyên dương ~N, \ (1 \leq N\leq 150000)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N \ (1 \leq A_i \leq 150000)~ là chỉ số sức mạnh của các Mỏ neo không gian.
• ~N-1~ dòng tiếp theo là các số nguyên dương ~u_i~, ~v_i~ và ~d_i~ ~(1 \le u_i, v_i \le N, \ u_i \neq v_i,\ 1 \le d_i \le 10^9)~ tương ứng với các cạnh của cây.

Output

• In ra một số nguyên duy nhất là đáp án của bài toán. Vì kết quả có thể rất lớn, hãy in ra phần dư của đáp án sau khi chia ~998244353~.

Scoring

• Subtask 1 ~(11p)~: ~N \leq 300~.
• Subtask 2 ~(16p)~: ~N \leq 2000~.
• Subtask 3 ~(27p)~: ~A_1 = A_2 = \ldots = A_N~.
• Subtask 4 ~(27p)~: ~u_i + 1 = v_i~ với ~i = 1, 2, \ldots, N - 1~.
• Subtask 5 ~(19p)~: Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

71

Notes

• ~f(1, 2) = 2~, ~f(1, 3) = 4~, ~f(1, 4) = 5~, ~f(1, 5) = 1~
• ~f(2, 3) = 6~, ~f(2, 4) = 3~, ~f(2, 5) = 9~
• ~f(3, 4) = 20~, ~f(3, 5) = 15~
• ~f(4, 5) = 6~

Kazuma có hai số nguyên ~N~ và ~M~. Megumin muốn đếm số lượng dãy ~A~ khác nhau có ~N~ phần tử thỏa mãn:

• ~A_i \in \mathbb{N}, \forall i = 1, 2, \ldots , N~,
• ~\sum_{i = 1}^N A_i = M~,
• ~A_1 \oplus A_2 \oplus \ldots \oplus A_N = 0~. Ở đây ~\oplus~ là phép XOR nhị phân.

Hai dãy ~X, Y~ độ dài ~N~ được gọi là khác nhau nếu tồn tại vị trí ~i~ ~(1 \le i \le N)~ mà ~X_i \neq Y_i~. Dù là pháp sư có sức mạnh tối thượng, nhưng vì chỉ biết một loại phép thuật nên bài toán này vẫn rất khó với Megumin. Bạn hãy giúp Megumin nhé!

Input

• Gồm một dòng duy nhất chứa hai số ~N, M~ ~(1 \le N, M \le 10^5)~.

Output

• In ra duy nhất một số nguyên là số lượng dãy ~A~ thỏa mãn. Vì đáp án có thể rất lớn nên hãy in ra đáp án modulo ~998244353~.

Scoring

• Subtask 1 ~(5p)~: ~N = 2~
• Subtask 2 ~(21p)~: ~N, M \le 100~
• Subtask 3 ~(28p)~: ~M \le 20~
• Subtask 4 ~(30p)~: ~N, M \le 5000~
• Subtask 5 ~(16p)~: Không có giới hạn gì thêm.

Sample Input

3 6

Sample Output

9

Notes

Có 9 dãy ~A~ thỏa mãn:

• ~[1, 2, 3]~, ~[1, 3, 2]~, ~[2, 1, 3]~, ~[2, 3, 1]~, ~[3, 1, 2]~, ~[3, 2, 1]~,
• ~[0, 3, 3]~, ~[3, 0, 3]~, ~[3, 3, 0]~.