Trong cuộc thám hiểm gần đây, bạn đã phát hiện ra một hầm kho báu có thể được biểu diễn dưới dạng lưới với ~N~ hàng (được đánh số từ ~1~ đến ~N~) và ~M~ cột (được đánh số từ ~1~ đến ~M~). Ô ở hàng ~r~ và cột ~c~ được ký hiệu là ~(r, c)~. Ô ~(r, c)~ chứa kho báu nếu ~A_{r,c} = 1~, và ô đó trống nếu ~A_{r,c} = 0~.

Có ~Q~ kịch bản độc lập. Đối với mỗi kịch bản, bạn bắt đầu ở ô ~(R, C)~ và bạn muốn mang chính xác ~K~ kho báu trở về ô ~(R, C)~. Trong một giây, bạn có thể di chuyển đến bất kỳ ô nào kề bên theo hướng ngang, dọc hoặc chéo với ô bạn đang đứng, như được minh họa trong hình dưới đây. Do kho báu rất lớn, bạn chỉ có thể mang mỗi lần một kho báu, nghĩa là bạn phải mang kho báu trở về ô ~(R, C)~ trước khi lấy kho báu tiếp theo hoặc để hoàn thành kịch bản. Hành động nhặt hoặc bỏ kho báu không tốn thời gian.

Đối với mỗi kịch bản, xác định thời gian tối thiểu cần thiết (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~. Vì tất cả các kịch bản đều độc lập với nhau, nên sau mỗi kịch bản, các kho báu sẽ được trở lại vị trí ban đầu.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 1000~).
• Mỗi dòng trong ~N~ dòng tiếp theo bao gồm một chuỗi nhị phân ~A_i~ có độ dài ~M~. Ký tự thứ ~j~ của chuỗi ~A_i~ mô tả ô ~(i, j)~: là ~1~ nếu ô ~(i, j)~ chứa kho báu và là ~0~ nếu ô ~(i, j)~ trống. Số lượng kho báu trong hầm ít nhất là một.
• Dòng tiếp theo chứa một số nguyên ~Q~ (~1 \leq Q \leq 2 \times 10^4~).
• Mỗi dòng trong ~Q~ dòng tiếp theo gồm ba số nguyên ~R~, ~C~ và ~K~ (~1 \leq R \leq N~; ~1 \leq C \leq M~; ~1 \leq K~) mô tả mỗi kịch bản. Giá trị của ~K~ không vượt quá số lượng kho báu trong hầm.

Output

• Đối với mỗi kịch bản, xuất ra một số nguyên trên một dòng riêng biệt biểu thị thời gian tối thiểu (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~.

Sample

Input 1

5 5
11000
01011
10111
00101
10010
6
1 1 1
1 2 4
3 1 13
1 4 5
2 5 3
3 3 8

Output 1

0
8
64
16
4
20

Input 2

1 6
000111
3
1 1 2 
1 1 1
1 6 3

Output 2

14
6
6

Hiện tại, bạn đang nghiên cứu một thuật toán duyệt cây được gọi là Depth First Search - DFS. Giả sử bạn có một cây gốc gồm ~n~ nút (được đánh số từ ~1~ đến ~n~) với độ sâu là ~K~ (được đánh số từ ~1~ đến ~K~). Gốc cây (nút ở độ sâu ~1~) được đặt tại nút ~1~. Tất cả các lá đều nằm ở cùng một độ sâu, tức là ở độ sâu ~K~. Nút ~i~ có một mảng các nút con ~adj_i~ (có thể trống nếu ~i~ là lá). Mã giả của thuật toán được trình bày như sau:

DFS(u, depth):
    khởi tạo res là một mảng rỗng
    thêm depth vào cuối của res

    duyệt từng đỉnh v trong adj[u]:
        khởi tạo D là mảng kết quả của DFS(v, depth + 1)
        duyệt từng x thuộc D:
            thêm x vào cuối res

    return res

Ví dụ, giá trị trả về của DFS(1, 1) đối với cây bên trái và cây bên phải lần lượt là ~[1, 2, 3, 3, 3]~ và ~[1, 2, 3, 2, 3]~.

Ký hiệu ~f_K(n)~ là số lượng các giá trị trả về khác biệt của DFS(1, 1) trên tất cả các cây gồm ~n~ nút và tất cả các lá đều nằm ở độ sâu ~K~.

Bạn được cho ~M~ số nguyên: ~A_1, A_2, \ldots, A_M~. Xác định giá trị của ~f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)~.

Vì kết quả có thể rất lớn, hãy tìm đáp án modulo ~998,244,353~.

Input

• Dòng đầu tiên gồm hai số nguyên ~K~ và ~M~ (~1 \leq K, M \leq 10^5~).
• Dòng tiếp theo gồm ~M~ số nguyên ~A_i~ (~K \leq A_i \leq 2 \times 10^5~).

Output

• In ra một số nguyên duy nhất đại diện cho giá trị của ~f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)~ modulo ~998,244,353~.

Subtask

• Subtask ~1~: ~a_i \le 8~ ~(20\%)~
• Subtask ~2~: ~a_i \le 1000~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm.

Sample

Input 1

3 2
5 6

Output 1

6

Explanation 1

• ~f_3(5) = 2~, ~f_3(6) = 3 ~. Hình dưới đây là minh họa cho các dạng cây có ~6~ đỉnh.

Input 2

69696 1
200000

Output 2

920040834

Bảo và Lâm là đôi bạn thân. Cả hai bạn rất đam mê đồ công nghệ nên cả hai muốn đến khu mua sắm công nghệ Shiro. Ở con đường Shiro, có ~n~ cửa hàng xếp thành hàng ngang được đánh số từ ~1~ đến ~n~.

Thời nay, việc tìm hiểu một cửa hàng mà không cần vào trực tiếp ở quầy là một điều dễ dàng. Chỉ cần tìm ra page, web của những cửa hàng đó, bạn có thể tìm trước các sản phẩm mà mình muốn mua thay vì đến tận nơi để xem. Do đó, trước khi đến trung tâm công nghệ Shiro đông đúc, Bảo và Lâm sẽ ở nhà tìm hiểu hết ~n~ cửa hàng và sau đó mới đến tại cửa hàng để mang về. Sau khi đã tính toán xong, cả hai bạn đã thống kê lại lượng tiền cần chi ra đối với cửa hàng thứ ~i~ là ~a_i~ đồng. Và với mọi cửa hàng ~i~, Bảo và Lâm cũng thống nhất rằng nếu đã mua thì phải mua đúng ~a_i~ đồng như đã tính toán ở nhà hoặc là không mua gì cả.

Sau khi đã có bản thống kê chi tiêu, cả hai bạn bắt đầu di chuyển đến khu Shiro để mua sắm. Bảo sẽ chọn cửa hàng bắt đầu di chuyển đó là cửa hàng ~l~, nghĩa là sau đó, cả hai bạn trẻ sẽ đến các cửa hàng ~l+1,l+2,\ldots~ tức là cả hai sẽ tới cửa hàng ~i~ rồi mới sang cửa hàng ~i+1~ và bắt đầu từ vị trí ~l~. Tuy nhiên, lâm nhận thấy rằng lúc này cả hai chỉ có trong tay số tiền là ~k~ đồng nên có thể sẽ không chi tiêu được theo dự định tại tất cả các cửa hàng từ vị trí ~l~ đến vị trí ~n~. vì vậy, Lâm quyết định đưa ra hai giá trị ~u,v~ ~(u \le v)~ làm tiêu chí mua sắm. Tại cửa hàng ~i~, nếu giá trị ~a_i~ không nằm trong đoạn ~[u,v]~ thì Bảo và Lâm sẽ bỏ qua và tiếp tục di chuyển đến cửa hàng thứ ~i+1~ (nếu ~i<n~). Ngược lại, với ~u \le a_i \le v~, cả hai bạn sẽ bỏ ra ~a_i~ đồng như dự tính nếu như số tiền còn lại vẫn ~(a_i \le k)~. Tuy nhiên, nếu số tiền còn lại không đủ để mua như dự định ~(a_i > k)~ thì cả hai sẽ rất buồn chán và đi về luôn mà không quan tâm các cửa hàng sau đó nữa. Đương nhiên nếu mua được theo dự tính thì số tiền mà hai bạn còn lại cho chuyến mua sắm lần này sẽ giảm đi ~a_i~ đồng.</p>

Như vậy, số lượng cửa hàng có thể mua sắm được trong chuyến đi lần này phụ thuộc vào việc cả hai bạn chọn ~l,u,v~ và số tiền mà cả hai mang theo ~k~. Bạn hãy giúp hai bạn trẻ tính xem số cửa hàng mà các bạn đi qua là bao nhiêu? Lưu ý rằng, những cửa hàng có giá trị ~a_i~ không nằm trong đoạn ~[u,v]~ vẫn xem là đi qua vì sau đó cả hai có thể di chuyển tiếp, còn cửa hàng có giá trị ~a_i~ thuộc đoạn ~[u,v]~ nhưng lại có ~a_i > k~ thì xem như không đi qua vì đây là cửa hàng làm cho cả hai bạn thất vọng.

Có ~q~ giả thuyết cho các giá trị ~l,u,v,k~ và vẫn dựa trên ~n~ giá trị ~a_1, a_2, \ldots, a_n~ dự định ban đầu của cả hai bạn. Với mỗi giả thuyết, bạn hãy tính xem cả hai bạn Bảo và Lâm sẽ đi qua được bao nhiêu cửa hàng, bạn cần in ra số lượng đó.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 10^5~) là số lượng cửa hàng.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) là ~n~ dự định tương ứng với ~n~ cửa hàng của hai bạn.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~l~, ~u~, ~v~, và ~k~ (~1 \leq l \le n~, ~1 \leq u \le v \le 10^9~, ~1 \leq k \le 10^9~) mô tả một giả thiết.

Output

• Với mỗi giả thuyết, hãy đưa ra số lượng cửa hàng mà cả hai bạn đi qua.

Scoring

• Subtask ~1~ (~20\%~ số điểm): Các giả thuyết có ~k~ bằng nhau và ~u=1~, ~v=10^9~.
• Subtask ~2~ (~20\%~ số điểm): ~a_i \leq 500~ với mọi ~1 \leq i \leq n~.
• Subtask ~3~ (~20\%~ số điểm): Các giả thiết có ~v - u \le 5~.
• Subtask ~4~ (~20\%~ số điểm): Các giả thiết có ~u = 1~.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input 1

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

Sample Input 2

3
7
2

Explanation

• Ở giả thiết thứ nhất, cả hai bạn sẽ đi qua cửa hàng ~4~, mua hết ~2~ đồng và còn lại ~5~ đồng. Đến cửa hàng ~5~, do các bạn dự định mua ~10~ đồng nhưng ở trường hợp này cả hai chỉ muốn mua tại các cửa hàng có dự định trong khoảng ~[1, 5]~ nên cả hai sẽ đi tiếp đến cửa hàng ~6~. Đến đây các bạn vẫn có thể mua và số tiền còn lại bây giờ là ~0~ đồng. Đến cửa hàng thứ ~7~, cả hai bạn rất buồn vì có số tiền mua sắm dự định nằm trong tiêu chí nhưng lại không đủ tiền. Nên cả hai chỉ nhớ những cửa hàng đã đi qua là ~4, 5, 6~. Còn cửa hàng ~7~ thì cả hai không muốn phải nhớ đến nữa.
• Ở giả thiết thứ hai, cả hai sẽ di chuyển từ cửa hàng ~1~, lần lượt đi qua các cửa hàng và chỉ có cửa hàng ~4~ là mua được theo đúng tiêu chí, và số tiền mua còn lại vẫn còn đủ để mua. Do đó cả hai đã đi qua toàn bộ ~7~ cửa hàng.
• Ở giả thiết thứ ba, cả hai sẽ di chuyên từ cửa hàng ~1~, mua theo dự định và còn ~11~ đồng. Sang cửa hàng thứ ~2~, vẫn có thể mua theo dự định và còn ~5~ đồng. Sang cửa hàng thứ ~3~, mặc dù số tiền bỏ ra dự định nằm trong tiêu chí nhưng lại không đủ tiền, cả hai thất vọng đi về và không muốn nhớ đến cửa hàng thứ ~3~ này nữa. Do đó chỉ xem như cả hai chỉ đi qua các cửa hàng ~1~ và ~2~.

Cho một dãy số nguyên không âm ~a~ gồm ~n~ phần tử.

Gọi ~{s_1, s_2, \ldots, s_k}~ (~s_1 < s_2 < \cdots < s_k~) là tập hợp tất cả các số nguyên không âm có thể là kết quả của phép XOR của một dãy con (không nhất thiết liên tiếp và có thể rỗng) của ~a~.

Cho hai số nguyên ~L~ và ~R~, hãy in ra ~s_L, s_{L+1}, \ldots, s_R~ theo thứ tự này.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~N~, ~L~ và ~R~ (~1 \leq N \le 2 \times 10^5, 1 \le L \le R \le k~, ~R - L + 1 \le 2 \times 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~. ~(0 \le a_i \le 10^{18})~.

Output

• In ra ~s_i~ ~(1 \le L \le i \le R)~ theo thứ tự tăng dần của ~i~.

Subtask

• Subtask ~1~: ~n \le 1000, a_i \le 1000~ ~(30\%)~
• Subtask ~2~: ~L = R = k~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm. ~(40\%)~

Sample

Input 1

4 1 8
14 5 14 6

Output 1

0 3 5 6 8 11 13 14