Cho ~1~ xâu ký tự chứa toàn chữ số khác ~0~. Có ~2~ bài toán con:

1. Có bao nhiêu xâu con liên tiếp tạo thành ~1~ số chia hết cho ~33~? Xâu con dù giống nhau nhưng ở vị trí khác nhau được coi là khác nhau.
2. Số (được tạo từ xâu con liên tiếp) lớn nhất chia hết cho ~33~ là số nào? Nếu không có số nào in ra ~-1~.

Input

Dòng đầu chứa ~1~ xâu kí tự ~s~. Dòng tiếp theo chứa chỉ số của bài toán con.

Output

In ra đáp án trên 1 dòng duy nhất.

SUBTASKS

~30\%~ số điểm ~|s| \leq 1000~. ~70\%~ số điểm ~|s| \leq 1000000~.

Sample Input 1

1223
1

Sample Output 1

0

Sample Input 2

12311
2

Sample Output 2

231

Cho dãy ~P~ là một hoán vị của ~{1 \dots N}~. Gọi ~F(P)~ là số bước ít nhất để đưa ~P~ về dãy ~\{1 \dots N\}~, trong đó mỗi bước được phép chọn hai vị trí ~i~, ~j~ và đổi chỗ giá trị ~P[i]~ và ~P[j]~.

Cho ~C~ truy vấn đổi chỗ ~P[x]~ và ~P[y]~, sau mỗi truy vấn in ra ~F(P)~. Mọi phép đổi chỗ là cố định, tức là sau mỗi truy vấn ~P~ không quay trở lại như cũ.

Input

Dòng ~1~: ~2~ số ~N~ và ~C~

Dòng ~2~: ~N~ số ~P[1]~, ~P[2]~, ~\dots~, ~P[N]~ là dãy ~P~ ban đầu

Dòng ~2 + i~: ~2~ số ~x~, ~y~ là tham số của truy vấn thứ ~i~

Output

In ra ~C~ dòng, dòng thứ ~i~ in ~1~ số duy nhất là ~F(P)~ sau truy vấn thứ ~i~.

Giới hạn

• ~2 \leq N \leq 10^5~, ~1 \leq C \leq 5 \times 10^4~, ~1 \leq x < y \leq N~
• ~25\%~: ~N~, ~C \leq 10^3~
• ~75\%~: Không có ràng buộc gì thêm

Sample Input 1

3 2
2 3 1
2 3
2 3

Sample Output 1

1
2

Sample Input 2

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

Sample Output 2

3
2
1

Giải thích

Test ~1~: ~P = {2, 3, 1} \rightarrow {2, 1, 3} \rightarrow {2, 3, 1}~

Tournament là một đồ thị mà giữa ~2~ đỉnh bất kì có đúng một cạnh có hướng ~(1~ trong ~2~ chiều). ~F(G)~ là số đường đi Hamilton (đi qua mỗi đỉnh đúng ~1~ lần) của Tournament ~G~.

Tính tổng của các ~F(G)~, với ~G~ là tournament có ~N~ đỉnh và không chứa chu trình nào có độ dài chia hết cho ~D~.

Input

Dòng đầu và duy nhất chứa ~2~ số nguyên ~N~, ~D~ ~(1 \leq N \leq 100000~, ~3 \leq D \leq N + 1)~.

Output

In ra số dư của kết quả khi chia cho ~998244353~.

Giới hạn

~50\%~ số test có ~D \leq 100~

Sample Input 1

4 3

Sample Output 1

24

Sample Input 2

5 4

Sample Output 2

480

Cho một bảng ~2 \times n~, mỗi ô chứa ~1~ số, một hình chữ nhật được gọi là tốt nếu như tổng các số trong nó bằng ~0~. Chia bảng đã cho thành nhiều hình chữ nhật tốt nhất có thể sao cho một ô dùng nhiều nhất một lần (không cần phải dùng hết tất cả các ô)

Input

• Dòng đầu tiên ghi số ~n~.
• Dòng thứ ~2~ và ~3~, mỗi dòng ghi ~n~ số thể hiện bảng.

Output

Một số duy nhất thể hiện số hình chữ nhật lớn nhất có thể chia

Giới hạn

• Trong tất cả các test, có: ~|a(i)| \leq 10^9~
• ~80\%~ số test: ~n \leq 1000~.
• ~20\%~ số test còn lại: ~n \leq 10^5~

Sample Input 1

6
70 70 70 70 70 -15
90 -60 -30 30 -30 15

Sample Output 1

3

Sample Input 2

4
0 -1 0 0
0 0 1 0

Sample Output 2

6