Ở phòng thí nghiệm có một khay nuôi cấy vi khuẩn Petri có dạng hình chữ nhật kích thước ~n \times m~. Ban đầu, ở ô ~(i,j)~ ~(1 \le i \le n, 1 \le j \le m)~ có ~a_{i,j}~ ~(0 \le a_{i,j} \le 2)~ con vi khuẩn. Ở biên của khay không có con vi khuẩn nào; nói cách khác, nếu ~i \in \{1, n\}~ hoặc ~j \in \{1, m\}~ thì ~a_{i,j}=0~.

Sau một ngày, mỗi vi khuẩn ở ô ~(i,j)~ sẽ biến thành ~4~ con vi khuẩn ở các ô ~(i-1,j)~, ~(i,j-1)~, ~(i,j+1)~, ~(i+1,j)~. Bạn đến phòng thí nghiệm muộn một ngày nên chỉ biết rằng ở ô ~(i,j)~ đang có ~b_{i,j}~ con vi khuẩn. Hãy tìm lại số lượng vi khuẩn ~a_{i,j}~ ở mỗi ô ban đầu.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 100)~ — kích thước của khay.

Trong mỗi dòng của ~n~ dòng tiếp theo chứa ~m~ số nguyên không âm ~b_{i,j}~ ~(0 \le b_{i,j} \le 8)~ — số lượng vi khuẩn của ô ~(i,j)~ sau một ngày.

Output

Trong mỗi dòng của ~n~ dòng chứa ~m~ số nguyên không âm ~a_{i,j}~ ~(0 \le a_{i,j} \le 2)~ — số lượng vi khuẩn của ô ~(i,j)~ tại thời điểm ban đầu.

Dữ liệu đề bài đảm bảo luôn tồn tại giá trị ~a_{i,j}~ thỏa mãn.

Scoring

Sample Input 1

4 4
0 1 0 0
1 0 2 0
0 2 0 1
0 0 1 0

Sample Output 1

0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0

Sample Input 2

5 5
0 0 2 0 0
0 4 0 4 0
2 0 8 0 2
0 4 0 4 0
0 0 2 0 0

Sample Output 2

0 0 0 0 0
0 0 2 0 0
0 2 0 2 0
0 0 2 0 0
0 0 0 0 0

Notes

Ở ví dụ đầu tiên ta thấy rằng:

• Sau một ngày, vi khuẩn ở ô ~(2,2)~ biến thành ~4~ con vi khuẩn ở các ô ~(1,2)~, ~(2,1)~, ~(2,3)~, ~(3,2)~.

• Sau một ngày, vi khuẩn ở ô ~(3,3)~ biến thành ~4~ con vi khuẩn ở các ô ~(2,3)~, ~(3,2)~, ~(3,4)~, ~(4,3)~.

Xét mảng ~a~ gồm ~n~ phần tử. Gọi $$f(a) = \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} a_i \oplus a_j$$

Cho hai số ~n, m~ nguyên dương. Gọi ~S~ là tập các mảng ~a~ độ dài ~n~ thoả mãn ~0 \le a_i < 2^m~.

Tính ~\sum_{a \in S} f(a)~.

Input

Nhập một dòng duy nhất là hai số nguyên dương ~n, m~ (~2 \le n \le 10^5, 1 \le m \le 10^5~).

Output

In ra yêu cầu đề bài. Vì đáp án có thể rất lớn, in đáp án modulo ~998 \,244 \, 353~.

Scoring

Sample Input 1

2 1

Sample Output 1

2

Notes

• ~f([0, 0]) = 0 \oplus 0 = 0~

• ~f([0, 1]) = 0 \oplus 1 = 1~

• ~f([1, 0]) = 1 \oplus 0 = 1~

• ~f([1, 1]) = 1 \oplus 1 = 0~

Đáp án là ~0 + 1 + 1 + 0 = 2~.

Ông già Noel có ~N~ loại quà, trong đó loại thứ ~i~ gồm ~a_i~ hộp quà giống nhau. Việc phát quà Noel cho các bé được ông thực hiện như sau:

1. Đầu tiên, ông già Noel chia toàn bộ các hộp quà vào ~M~ túi quà có sẵn, được ông xếp thành hàng ngang và đánh số từ ~1~ đến ~M~ (tăng dần từ trái sang phải).

2. Máy tính chọn ra ngẫu nhiên một cặp số (~L, R~) thỏa mãn ~1 \le L \le R \le M~, sau đó các túi quà có chỉ số từ ~L~ đến ~R~ sẽ được mang lên xe tuần lộc để phân phát cho trẻ em trên khắp thế giới. Lưu ý rằng, mọi cặp số (~L, R~) có xác suất được chọn là như nhau.

Ở bước 2, ta gọi số loại quà khác nhau trong các túi từ ~L~ đến ~R~ là độ đa dạng của chúng. Ta coi một túi không có quà có độ đa dạng là ~0~. Vì không muốn đứa trẻ nào nhận ra hai hộp quà giống nhau nên từ bước 1, ông già Noel sẽ chủ động chia quà vào các túi sao cho độ đa dạng đạt giá trị kỳ vọng lớn nhất.

Hãy giúp ông già Noel tính giá trị kỳ vọng lớn nhất của độ đa dạng, hoặc số cách chia quà để đạt được giá trị kỳ vọng trên.

Input

• Dòng đầu tiên gồm số nguyên ~T~ (~1 \le T \le 2~).

• Dòng thứ hai gồm hai số nguyên ~N~ và ~M~ (~1 \le N \le 2 \cdot 10^5, 1 \le M \le 10^9~) — số loại quà và số túi quà của ông già Noel.

• Dòng thứ ba gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le 10^6~) — số hộp quà của mỗi loại quà.

Output

• Nếu ~T = 1~, in ra một số nguyên là giá trị kỳ vọng lớn nhất của độ đa dạng, lấy dư cho ~998\,244\,353~.

• Nếu ~T = 2~, in ra một số nguyên là số cách chia quà để độ đa dạng đạt giá trị kỳ vọng lớn nhất, lấy dư cho ~998\,244\,353~.

Scoring

Sample Input 1

1
2 4
3 4

Sample Output 1

698771049

Sample Input 2

2
2 4
3 4

Sample Output 2

4

Notes

Hai ví dụ trên chỉ khác nhau ở giá trị của ~T~. Cách chia để độ đa dạng đạt được giá trị kỳ vọng lớn nhất là cho ~3~ túi chứa các loại quà ~1~ và ~2~, túi còn lại chỉ chứa loại quà ~2~.

• Giá trị kỳ vọng lớn nhất là ~\frac{19}{10} \equiv 698\,771\,049 \pmod {998\,244\,353}~.

• Có tổng cộng ~4~ cách chia quà như trên (mỗi vị trí của túi chỉ chứa loại quà ~2~ tương ứng với một cách chia).

Cho một dãy số nguyên gồm ~n~ số ~a_1, a_2, \ldots, a_n~.

Gọi ~C(x)~ là số cách chọn hai số ~a_i~, ~a_j~ (~1 \le i < j \le n~), sao cho ~a_i + a_j = x~.

Ta có đa tập hợp (multiset) ~S~ ban đầu rỗng. Ta cần thực hiện ~q~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• add ~x~: Thêm phần tử ~x~ (~|x| \le 10^9~) vào ~S~.

• del ~x~: Xóa phần tử ~x~ (~|x| \le 10^9~) khỏi ~S~ (nếu trong ~S~ gồm nhiều phần tử ~x~, ta chỉ xóa một phần tử ~x~ ra khỏi ~S~). Dữ liệu đảm bảo tồn tại ~x~ trong ~S~ khi thực hiện thao tác xoá.

• ask ~l~ ~r~: Tính giá trị của ~F(l, r)~ (~-10^9 \le l \le r \le 10^9~), với $$F(l, r) = \sum_{l \le x \le r, x \in S} C(x)$$

• roll ~t~: Quay lại thời điểm trước khi thực hiện truy vấn thứ ~t~ (~1 \le t < i~), với ~i~ là thời điểm của truy vấn hiện tại.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~, ~q~ (~1 \le n, q \le 10^5~).

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^5~).

~q~ dòng tiếp theo gồm ~q~ truy vấn có dạng trên.

Output

Với mỗi truy vấn ask, in ra một số nguyên trên một dòng.

Scoring

Sample Input 1

6 6
1 1 3 2 5 6
add 3
del 3
roll 2
add 5
ask 3 5
ask 5 10

Sample Output 1

3
1

Vào năm 2049, do phần lớn người chơi đã cảm thấy chán nản với trò chơi Wordle, nhà phát hành quyết định sản xuất phiên bản dài hơn (và hi vọng hay hơn) của nó, gọi là Lomkdle. Lomkdle hoạt động như sau:

Nhiệm vụ của người chơi là cần tìm ra một từ ~S~ gồm ~N~ chữ cái tiếng Anh hoa, sử dụng ~M~ lần đoán. Mỗi lần đoán, người chơi sẽ đưa ra một từ ~T~ cũng gồm ~N~ chữ cái tiếng anh in hoa. Sau khi đưa ra từ, máy sẽ tô màu các chữ của ~T~ bằng một trong ba màu xanh, vàng, đen với ý nghĩa như sau:

• Nếu chữ ~T_i~ được tô màu xanh, thì ~S_i = T_i~.

• Nếu chữ ~T_i~ được tô màu vàng, thì ~T_i~ tồn tại trong ~S~, nhưng mà ~S_i \neq T_i~.

• Nếu chữ ~T_i~ được tô màu đen, thì ~T_i~ không xuất hiện thêm lần nào trong ~S~.

Nếu chữ cái ~c~ xuất hiện nhiều lần trong ~T~, thì các chữ cái đó sẽ được tô màu theo các bước lần lượt như sau:

• Các chữ cái có vị trí đúng thì sẽ được tô màu xanh.

• Từ trái qua phải, tô màu vàng cho những lần xuất hiện còn lại của ~c~ trong ~S~.

• Tô màu đen cho những chữ còn lại.

Ví dụ, nếu từ cần tìm ~S~ là AGGIN, thì các từ ~T~ được đoán sẽ được tô màu như sau:

Bedao vừa mới biết chơi Lomkdle nên đã dùng hết cả ~M~ lần đoán mà vẫn không biết được từ cần tìm ~S~ là gì. Hãy giúp Bedao tìm bất kì từ nào có thể là ~S~ dựa trên những từ ~T~ mà Bedao đã đoán!

Input

Dòng đầu tiên nhập số ~Q~ ~(1 \le Q \le 10)~ - số lượng test.

Với mỗi test, dòng đầu gồm hai số ~N, M~ ~(1 \le N \le 500, 1 \le M \le 500)~.

~M~ dòng sau, mỗi dòng gồm hai xâu ~T_i~ và ~C_i~ — xâu mà Bedao đoán ở lượt thứ ~i~ và cách tô màu của nó (~\lvert T_i \rvert = \lvert C_i \rvert = N~, ~T_{ij} \in \{A,B,\dots,Z\}~, ~C_{ij} \in \{G,Y,B\}~ — tương ứng với màu xanh, vàng, đen).

Luôn tồn tại ít nhất một từ ~S~ thỏa mãn mọi lần đoán.

Output

Với mỗi test, in ra một từ có thể là ~S~.

Scoring

Sample Input 1

1
5 6
ANGER GYGBB
GRINS YBYYB
GAGGY YYGBB
ZGGAA BGGYB
GGEZS YGBBB
AGGIN GGGGG

Sample Output 1

AGGIN

Kho báu của fextivity được anh ta cất giữ ở trong một két sắt. Chìa khóa để mở két sắt là một mật mã cho dưới dạng một xâu ~P~ gồm đúng ~52~ chữ cái tiếng Anh in thường và in hoa, mỗi chữ cái xuất hiện đúng một lần. Để giải mật mã, các nhà thám hiểm cần sử dụng một thiết bị đặc biệt do fextivity tạo ra có cách thức hoạt động như sau:

• Gọi các kí tự của xâu ~P~ là ~P[0], P[1], \ldots, P[51]~.
• Định nghĩa một mảng vị trí ~pos~ với ý nghĩa: ~P[i] = c \Leftrightarrow pos[c] = i~.
• Người sử dụng đưa ra một xâu ~S~ có độ dài không vượt quá ~10~.
• Thiết bị sẽ trả về một xâu ~T~ được xác định như sau:
  • ~T[0] = S[0]~.
  • Với ~i > 0~, ~T[i]~ là kí tự ở chính giữa ~T[i - 1]~ và ~S[i]~ trên xâu ~P~. Cụ thể đặt ~x = pos[T[i - 1]]~ và ~y = pos[S[i]]~, ta có: $$T[i] = \begin{cases}P \left[ \left \lfloor \frac{x + y}{2} \right \rfloor \right] & (y < x) \\ P \left[ \left \lceil \frac{x + y}{2} \right \rceil \right] & (y \ge x)\end{cases}$$

Với rất nhiều lần thử, những nhà thám hiểm đi trước đã tìm ra được kí tự đầu tiên của xâu ~P~. Tuy nhiên thiết bị đã cũ, bạn hãy tìm cách giải mật mã với ít lần sử dụng ít nhất có thể.

Output

Gồm một dòng duy nhất là xâu ~P~ cần tìm.

Interaction

Trước khi thực hiện truy vấn, bạn sẽ nhận được ở dòng đầu tiên kí tự duy nhất ~P[0]~ — kí tự đầu tiên của xâu kí tự ~P~ mà các nhà thám hiểm đã tìm được.

Để sử dụng thiết bị trên, yêu cầu in ra truy vấn theo dạng "? S" với ~S~ là xâu kí tự được sử dụng để thực hiện truy vấn. Sau đó, bạn sẽ nhận được xâu ~T~ là xâu kí tự kết quả.

Để in ra đáp án, yêu cầu in ra theo dạng "! P" với ~P~ là xâu kí tự cần tìm.

Scoring

Gọi ~Q~ là số lần sử dụng thiết bị: