Định nghĩa:

• Một hoán vị độ dài ~n~ là một dãy gồm ~n~ số nguyên, trong đó mỗi số nguyên từ ~1~ đến ~n~ xuất hiện đúng một lần.

• Ước chung lớn nhất giữa hai số nguyên ~x~ và ~y~, kí hiệu ~\gcd(x, y)~, là số nguyên dương lớn nhất chia hết cho cả ~x~ và ~y~.

• Một hoán vị ~p_1, p_2, \ldots, p_n~ được xem là hoán vị không nguyên tố cùng nhau nếu ~\gcd(p_{i-1} + p_i, p_i + p_{i+1}) > 1~ với mọi ~i~ từ ~2~ đến ~n-1~.

Cho số nguyên ~n~, hãy cho biết có tồn tại hoán vị không nguyên tố cùng nhau độ dài ~n~ hay không, và nếu có thì hãy chỉ ra một hoán vị như vậy.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Phần mô tả các test case như sau.

Mỗi test case chỉ gồm một dòng, chứa một số nguyên duy nhất ~n~ (~3 \le n \le 5 \cdot 10^5~) — độ dài hoán vị cần tìm.

Dữ liệu vào đảm bảo rằng tổng ~n~ qua tất cả các test không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test case, in ra kết quả theo định dạng sau:

• Nếu không tồn tại hoán vị như vậy, hãy in ra ~-1~.

• Ngược lại, hãy in ra ~n~ số nguyên ~p_1, p_2, \ldots, p_n~ — hoán vị không nguyên tố cùng nhau tìm được.

Nếu có nhiều hoán vị thỏa mãn, hãy in ra hoán vị bất kỳ.

Scoring

Tổng điểm của bài toán này là ~500~.

Sample Input 1

2
3
7

Sample Output 1

-1
1 3 7 5 4 2 6

Linh nhỏ đang sắp xếp một hàng gồm ~n~ tủ trưng bày cho một triển lãm đá quý. Tủ thứ ~i~ trưng bày một viên đá quý được gắn nhãn bằng một số nguyên không âm ~a_i~, hoặc là để trống — các tủ trống được ký hiệu bởi ~a_i = -1~. Với mỗi tủ trống, Linh có thể đặt vào đó một viên đá quý với bất kỳ nhãn số nguyên không âm nào mà cô ấy chọn.

Gọi ~\mathrm{MaxMex}(l, r)~ của đoạn ~a_l, a_{l + 1}, \ldots, a_r~ là mex^∗ lớn nhất có thể đạt được của các nhãn đá quý bằng cách đặt các viên đá quý có nhãn không âm vào tất cả các tủ trống bên trong đoạn đó.

Hãy giúp Linh tính ~\displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r)~.

Lưu ý rằng ~\mathrm{MaxMex}~ của các đoạn được tính độc lập với nhau. Tức là, nếu hai đoạn cùng chứa một tủ trống, Linh có thể chọn một viên đá cho tủ đó để tối đa hóa ~\mathrm{MaxMex}~ của một đoạn, và chọn một viên đá khác cho cùng tủ đó để tối đa hóa ~\mathrm{MaxMex}~ của đoạn còn lại.

∗ mex của một đa tập là số nguyên không âm nhỏ nhất không xuất hiện trong nó; ví dụ, ~\mathrm{mex}(\{0, 1, 1, 3\}) = 2~ và ~\mathrm{mex}(\{1, 2\}) = 0~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 5000~) — số lượng tủ trưng bày.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~a_i = -1~ hoặc ~0 \le a_i \le 10^9~) – nhãn của các viên đá trong tủ, với tủ trống có ~a_i = -1~.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — tổng ~\displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r)~.

Scoring

Sample Input 1

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

Sample Output 1

7
22
10

Notes

Trong test case đầu tiên, ~a = [0, 2, -1]~, với tủ thứ ba là tủ trống. Dưới đây mã giá trị ~\mathrm{MaxMex}~ của các đoạn chứa tủ thứ ~3~:

• ~\mathrm{MaxMex}(1, 3) = 3~. Đặt vào tủ 3 viên đá có nhãn ~1~, thu được ~\mathrm{mex}(\{0, 2, 1\}) = 3~.

• ~\mathrm{MaxMex}(2, 3) = 1~. Đặt vào tủ 3 viên đá có nhãn ~0~, thu được ~\mathrm{mex}(\{2, 0\}) = 1~.

• ~\mathrm{MaxMex}(3, 3) = 1~. Đặt vào tủ 3 viên đá có nhãn ~0~, thu được ~\mathrm{mex}(\{0\}) = 1~.

Kết quả thu được là:

$$\begin{array}{llllll} \displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r) \\ = \mathrm{MaxMex}(1, 1) & + \mathrm{MaxMex}(1, 2) & + \mathrm{MaxMex}(1, 3) & + \mathrm{MaxMex}(2, 2) & + \mathrm{MaxMex}(2, 3) & + \mathrm{MaxMex}(3, 3) \\ = 1 & + 1 & + 3 & + 0 & + 1 & + 1 \\ = 7 \end{array}$$

Có ~n~ em bé được đánh số từ ~1~ đến ~n~ và ~m~ cái kẹo được đánh số từ ~1~ đến ~m~. Cho mảng số nguyên ~a_1, a_2, \ldots, a_m~, cái kẹo thứ ~i~ được yêu thích bởi em bé thứ ~a_i~.

Bạn cần chia toàn bộ ~m~ cái kẹo cho các em bé. Mỗi cái kẹo phải được đưa cho đúng một em bé. Ban đầu, mọi em bé đều có độ vui là ~0~. Khi em bé ~x~ nhận kẹo thứ ~i~:

• Nếu ~x = a_i~, độ vui của em bé ~x~ tăng thêm ~2~;

• Nếu ~x \ne a_i~, độ vui của em bé ~x~ tăng thêm ~1~.

Một cách chia kẹo được gọi là vui vẻ khi độ vui của hai em bé bất kỳ chênh nhau không quá ~1~.

Hãy tìm một cách chia kẹo vui vẻ bất kỳ, hoặc chỉ ra rằng không tồn tại cách chia kẹo nào vui vẻ.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Phần mô tả các test case như sau.

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 2 \cdot 10^5~) — số lượng em bé và số lượng kẹo.

• Dòng thứ hai chứa ~m~ số nguyên ~a_1, a_2, \ldots, a_m~ (~1 \le a_i \le n~), trong đó ~a_i~ là em bé yêu thích cái kẹo thứ ~i~.

Đảm bảo rằng:

• tổng ~n~ qua tất cả các test case không quá ~2 \cdot 10^5~;

• tổng ~m~ qua tất cả các test case không quá ~2 \cdot 10^5~.

Output

Với mỗi test case:

• Nếu không tồn tại cách chia kẹo vui vẻ, in ra NO.

• Ngược lại, in ra YES. Sau đó in ra ~m~ số nguyên ~b_1, b_2, \ldots, b_m~, trong đó ~b_i~ là chỉ số của em bé nhận cái kẹo thứ ~i~.

  Nếu có nhiều cách chia kẹo vui vẻ, hãy in ra một cách thỏa mãn bất kỳ.

Scoring

Tổng điểm của bài này là ~1500~.

Sample Input 1

2
3 3
1 2 3
3 1
1

Sample Output 1

YES
1 2 3
YES
2

Notes

Trong test case đầu tiên, mỗi em đều nhận được một cái kẹo, và em nào cũng nhận được cái kẹo mà mình thích. Do đó, độ vui của tất cả các em đều là ~2~.

Trong test case thứ hai, cái kẹo duy nhất được phát cho em bé thứ hai. Vì em bé thứ hai không thích cái kẹo này, nên độ vui của em là ~1~, còn độ vui của hai em bé còn lại đều là ~0~.

Cũng trong ví dụ thứ hai, nếu ta chia chiếc kẹo này cho em bé thứ nhất, thì đây không phải là cách chia kẹo vui vẻ: độ vui của em bé ~1~ là ~2~, còn độ vui của em bé ~2~ là ~0~, do đó độ chênh lệch lớn hơn ~1~.

Đây là một bài toán chạy hai lần (run-twice communication).

Sau nhiều ngày yên bình ăn chuối, các Minion quyết định xây dựng một hệ thống giao chuối mới.

Có ~n~ trạm chuối, được đánh số từ ~1~ đến ~n~, và ~m~ đường hầm hai chiều giữa chúng. Các đường hầm tạo thành một đồ thị vô hướng đơn. Để tránh nhầm lẫn trong quá trình giao hàng, các Minion muốn tô màu cho mỗi trạm bằng một trong bốn màu, được đánh số từ ~1~ đến ~4~, sao cho bất kỳ hai trạm nào được nối bởi một đường hầm đều có màu khác nhau.

Kevin đã tìm được một cách tô màu hợp lệ cho toàn bộ bản đồ và đang rất háo hức để chia sẻ nó với Stuart. Tuy nhiên, Stuart đang ở phòng khác và không thể nhìn thấy cách tô màu của Kevin.

Để chia sẻ cách tô màu, Kevin chỉ được phép gửi cho Stuart một thông điệp rất ngắn: một mảng có độ dài không quá ~\lfloor n / 2 \rfloor~, trong đó mỗi phần tử phải là một số nguyên từ ~1~ đến ~4~.

Nhiệm vụ của bạn là viết một chương trình giúp cả hai Minion.

Chương trình sẽ được chạy hai lần:

• Ở lần chạy thứ nhất, chương trình của bạn đóng vai Kevin. Chương trình nhận vào đồ thị và một cách tô màu hợp lệ của đồ thị, và phải xuất ra thông điệp của Kevin.

• Ở lần chạy thứ hai, chương trình của bạn đóng vai Stuart. Chương trình nhận vào cùng đồ thị và thông điệp của Kevin, và phải xuất ra bất kỳ cách tô màu hợp lệ nào của đồ thị bằng các màu từ ~1~ đến ~4~. Lưu ý rằng cách tô màu của Stuart không nhất thiết phải giống với cách tô màu ban đầu của Kevin.

Input

Lần chạy thứ nhất

Dòng đầu tiên chứa chuỗi Kevin. Mục đích của điều này là để chương trình của bạn nhận ra đây là lần chạy đầu tiên, và nó nên hoạt động như Kevin.

Mỗi lần chạy chứa nhiều test case. Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 2 \cdot 10^5~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 3 \cdot 10^5~) — số lượng trạm chuối và đường hầm, tương ứng.

• Mỗi trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~), biểu thị một đường hầm giữa các trạm ~u_i~ và ~v_i~.

• Dòng cuối cùng chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 4~), trong đó ~a_i~ là màu của trạm ~i~ trong cách tô màu hợp lệ của Kevin.

Đảm bảo rằng cách tô màu đã cho là hợp lệ. Tức là, với mọi cạnh ~(u, v)~, ta có ~a_u \ne a_v~.

Lần chạy thứ hai

Dòng đầu tiên chứa chuỗi Stuart. Mục đích của điều này là để chương trình của bạn nhận ra đây là lần chạy thứ hai, và nó nên hoạt động như Stuart.

Mỗi lần chạy chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 2 \cdot 10^5~) — số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 3 \cdot 10^5~) — số lượng trạm chuối và đường hầm, tương ứng.

• Mỗi trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~), biểu thị một đường hầm giữa các trạm ~u_i~ và ~v_i~.

• Dòng tiếp theo chứa một số nguyên ~k~ (~0 \le k \le \lfloor n / 2 \rfloor~) — độ dài thông điệp của Kevin.

• Dòng tiếp theo chứa ~k~ số nguyên ~c_1, c_2, \ldots, c_k~ (~1 \le c_i \le 4~), biểu thị thông điệp của Kevin. Nếu ~k = 0~, dòng này để trống.

Đảm bảo rằng:

• Đồ thị không chứa khuyên và không có cạnh song song.

• Lần chạy thứ hai chứa đúng các bộ dữ liệu giống hệt lần chạy thứ nhất: cùng số lượng bộ dữ liệu, cùng các đồ thị, và cùng thứ tự các test case.

• Tổng ~n~ qua tất cả các test case không vượt quá ~2 \cdot 10^5~.

• Tổng ~m~ qua tất cả các test case không vượt quá ~3 \cdot 10^5~.

Output

Lần chạy thứ nhất

Với mỗi test case, hãy xuất thông điệp của Kevin theo định dạng sau:

• Trên dòng đầu tiên, xuất một số nguyên ~k~ (~0 \le k \le \lfloor n / 2 \rfloor~) — độ dài của thông điệp.

• Trên dòng thứ hai, xuất ~k~ số nguyên ~c_1, c_2, \ldots, c_k~ (~1 \le c_i \le 4~). Nếu ~k = 0~, dòng này có thể để trống.

Lần chạy thứ hai

Với mỗi test case, hãy xuất một dòng chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le 4~), trong đó ~b_i~ là màu mà Stuart gán cho trạm ~i~. Cách tô màu của Stuart phải hợp lệ. Nói cách khác, với mọi cạnh ~(u, v)~, phải có ~b_u \ne b_v~.

Interaction

Scoring

Tổng điểm của bài toán này là ~1750~.

Sample Input 1

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

Sample Output 1

2
3 2
1
3

Sample Input 2

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

Sample Output 2

4 3 2 1 3
1 2 3

Notes

Hai ví dụ tương ứng với hai lần chạy của cùng một chương trình. Lưu ý rằng ví dụ chỉ minh hoạ cách mà chương trình tương tác, không thể hiện cách mà đáp án đúng được suy luận ra.

Trong lần chạy đầu tiên, Kevin nhận được các đồ thị cùng với các cách tô màu hợp lệ. Anh ấy gửi các thông điệp ~(3, 2)~ cho đồ thị đầu tiên, và ~(3)~ cho đồ thị thứ hai.

Trong lần chạy thứ hai, Stuart nhận được cùng các đồ thị và các thông điệp do Kevin gửi, rồi xuất ra các cách tô màu ~(4,3,2,1,3)~ và ~(1,2,3)~ cho đồ thị thứ nhất và thứ hai, tương ứng.

Trong cả hai đồ thị, mọi cặp trạm kề nhau đều có màu khác nhau, nên các cách tô màu là hợp lệ. Lưu ý rằng các cách tô màu của Stuart không nhất thiết phải giống với các cách tô màu ban đầu của Kevin.

Tướng quân Thiên Quang đang chuẩn bị đối mặt với một cuộc tấn công quy mô lớn của kẻ thù. Để phòng thủ khu vực, ông đã thiết lập một mạng lưới gồm ~n~ tiền đồn được kết nối bởi ~m~ con đường núi hai chiều, tạo thành một đồ thị xương rồng liên thông: mỗi con đường thuộc về nhiều nhất một chu trình đơn^∗. Mỗi tiền đồn có thể chứa nhiều nhất một người lính. Ban đầu, tiền đồn ~i~ có một người lính đóng quân nếu ~a_i = 1~, và bị trống nếu ~a_i = 0~.

Tin tưởng phó tướng Bá Lộc của mình, Thiên Quang giao cho anh ta việc điều phối trận chiến và yêu cầu anh ta sắp xếp lại quân lính theo một cách bố trí mục tiêu mới ~b~ (trong đó ~b_i = 1~ nghĩa là tiền đồn ~i~ cuối cùng phải có một người lính, ~b_i = 0~ nghĩa là nó phải bị bỏ trống). Dữ liệu đảm bảo rằng ~\sum_{i=1}^n a_i = \sum_{i=1}^n b_i~. Để thực hiện điều đó, anh ta có thể di chuyển các người lính như sau:

• Trong một phút, Bá Lộc có thể chọn một người lính và di chuyển anh ta đến một tiền đồn trống kề cận.

Bá Lộc phải tìm cách đạt được cách bố trí mục tiêu càng nhanh càng tốt. Hãy giúp Bá Lộc tính thời gian tối thiểu để đạt được cách bố trí mục tiêu. Có thể chứng minh rằng luôn có thể đạt được cách bố trí mục tiêu ~b~ từ cách bố trí ~a~ trong các điều kiện đã cho.

∗ Chu trình đơn trong một đồ thị là một dãy các đỉnh ~v_1, v_2, \ldots, v_k~, sao cho:

• đỉnh ~v_i~ và ~v_{i+1}~ (~1 \le i < k~) có cạnh nối,

• đỉnh ~v_1~ và ~v_k~ có cạnh nối,

• ~v_i \ne v_j~ với mọi ~1 \le i < j \le k~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Mô tả của mỗi test case như sau:

• Dòng đầu chứa hai số nguyên ~n, m~ (~1 \le n \le 2 \cdot 10^5~; ~n - 1 \le m \le \lfloor 3(n-1)/2 \rfloor~) — số cứ điểm và số con đường.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, \ldots, a_n~ (~0 \le a_i \le 1~) — bố trí ban đầu (~a_i = 1~ nghĩa là cứ điểm ~i~ ban đầu có lính).

• Dòng thứ ba chứa ~n~ số nguyên ~b_1, \ldots, b_n~ (~0 \le b_i \le 1~) — bố trí mục tiêu (~b_i = 1~ nghĩa là cứ điểm ~i~ cuối cùng phải có lính).

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le n~; ~u \ne v~) mô tả một con đường. Không có con đường trùng nhau.

Đảm bảo rằng:

• Mạng lưới tạo thành một xương rồng liên thông,

• ~\sum n \le 5 \cdot 10^5~ trên mọi test case,

• ~\sum_{i=1}^n a_i = \sum_{i=1}^n b_i~.

Output

Với mỗi test case, in ra một số nguyên — số lần hành quân ít nhất để đạt được bố trí mục tiêu ~b~.

Scoring

Sample Input 1

3
3 2
1 0 0
0 0 1
1 2
2 3
1 0
1
1
5 4
1 1 0 0 0
0 0 0 1 1
1 2
2 3
3 4
4 5

Sample Output 1

2
0
6

Sample Input 2

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

Sample Output 2

1
2

Sample Input 3

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

Sample Output 3

1
4

Notes

Trong ví dụ đầu tiên, test 1, người lính ở tiền đồn ~1~ hành quân ~1 \to 2 \to 3~, mất ~2~ phút.

Trong ví dụ thứ hai, test 1, người lính ở tiền đồn ~1~ di chuyển trực tiếp đến tiền đồn trống ~3~ dọc theo con đường ~(3, 1)~, mất ~1~ phút.

Trong ví dụ thứ ba, test 2, hai người lính ở các tiền đồn ~2~ và ~4~ phải lần lượt đi đến các tiền đồn ~5~ và ~1~; mỗi người di chuyển một khoảng cách là ~2~, nên tổng cộng mất ~4~ phút.

————————–

Các test case trong ví dụ đầu tiên đều thỏa mãn subtask 2.

Các test case trong ví dụ thứ hai đều thỏa mãn subtask 3.

Một robot lau dọn được đặt trên sàn của một căn phòng hình chữ nhật, xung quanh được bao bởi các bức tường. Sàn gồm ~n~ hàng và ~m~ cột. Các hàng của sàn được đánh số từ ~1~ đến ~n~ theo thứ tự từ trên xuống dưới, và các cột của sàn được đánh số từ ~1~ đến ~m~ theo thứ tự từ trái sang phải. Ô tại giao điểm của hàng thứ ~r~ và cột thứ ~c~ được ký hiệu là ~(r,c)~. Vị trí ban đầu của robot là ~(r_b, c_b)~.

Trong một giây, robot di chuyển ~dr~ hàng và ~dc~ cột; tức là sau một giây, robot đi từ ô ~(r, c)~ đến ô ~(r + dr, c + dc)~. Ban đầu, ~dr = 1~, ~dc = 1~. Nếu có một bức tường dọc (tường bên trái hoặc bên phải) theo hướng di chuyển, thì ~dc~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dc~ là ~-dc~. Tương tự, nếu có một bức tường ngang (tường phía trên hoặc phía dưới) theo hướng di chuyển, thì ~dr~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dr~ là ~-dr~.

Mỗi giây (bao gồm cả thời điểm trước khi robot bắt đầu di chuyển), các ô nằm trên cùng hàng hoặc cùng cột với vị trí hiện tại của robot sẽ được con robot lau sạch một lần. Ô vị trí hiện tại của con robot cũng chỉ được lau sạch một lần.

Tại thời điểm ~t~, định nghĩa:

• độ sạch của một ô trên sàn là số lần mà ô đó được lau sạch,

• độ sạch của sàn nhà là độ sạch nhỏ nhất trong số các ô trên mặt sàn.

Cho kích thước sàn ~n~ và ~m~, số nguyên ~k~, cùng vị trí ban đầu của robot ~(r_b, c_b)~. Hãy tìm thời điểm ~t~ nhỏ nhất sao cho khi robot lau sàn đến thời điểm ~t~, sàn nhà có độ sạch là ~k~.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 1000~). Phần mô tả các test case như sau.

Mỗi test case chỉ gồm một dòng, chứa năm số nguyên ~n~, ~m~, ~k~, ~r_b~, ~c_b~ (~2 \le n, m \le 20\,000~, ~1 \le k \le 10^9~, ~1 \le r_b \le n~, ~1 \le c_b \le m~) — kích thước của sàn nhà, độ sạch của sàn nhà cần đạt được, và vị trí ban đầu của robot.

Đảm bảo rằng:

• tổng ~n~ qua các test case không quá ~20\,000~,

• tổng ~m~ qua các test case không quá ~20\,000~.

Output

Với mỗi test case, in ra một số nguyên — thời gian tối thiểu để sàn nhà đạt được độ sạch ~k~.

Scoring

Sample Input 1

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

Sample Output 1

7
9
3
19

Notes

Hình trong đề bài là minh họa cho ví dụ đầu tiên.

Trong ví dụ thứ hai, sàn có kích thước ~9\times 8~, mỗi ô cần được lau sạch ít nhất ~k=1~ lần. Robot xuất phát tại ô ~(5, 6)~.

Trong ví dụ thứ ba, sàn có kích thước ~3\times 3~, mỗi ô cần được lau sạch ít nhất ~k=2~ lần. Robot xuất phát tại ô ~(1, 2)~.

Trong ví dụ thứ tư, sàn có kích thước ~2\times 2~, mỗi ô cần được lau sạch ít nhất ~k=10~ lần. Robot xuất phát tại ô ~(1, 1)~. Sau mỗi giây, hai ô ~(1, 2)~ và ~(2, 1)~ đều được lau. Còn ô ~(1, 1)~ và ô ~(2, 2)~ chỉ được lau 1 lần sau 2 giây. Ô ~(1, 1)~ sẽ được lau ~10~ lần sau ~18~ giây, còn ô ~(2, 2)~ sẽ được lau ~10~ lần sau ~19~ giây. Do đó, đáp án là ~19~.

Với hai số nguyên dương ~n~ và ~m~ bất kỳ, định nghĩa giá trị của ~f(n,m)~ như sau:

• Xét dãy số ~a~ gồm ~n~ phần tử, ban đầu ~a_i=0~ với mọi ~i~ từ ~1~ đến ~n~.

• Thực hiện thao tác sau đúng ~m~ lần: Chọn một chỉ số ~i~ ngẫu nhiên từ ~1~ đến ~n~, sau đó tăng ~a_i~ lên ~1~ đơn vị. Trong mỗi thao tác, mỗi chỉ số đều có xác suất được chọn là ~\frac{1}{n}~.

• Khi đó, ~f(n,m)~ là xác suất để sau khi thực hiện các thao tác, dãy ~a~ là độ dài các cạnh của một đa giác lồi gồm ~n~ đỉnh.

Bạn được cho hai số nguyên dương ~n~ và ~k~. Nhiệm vụ của bạn là xác định giá trị của ~f(n,n), f(n,n+1), \dots, f(n,n+k-1)~ khi chia dư cho ~998\,244\,353~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 50\,000~). Mô tả của mỗi test case như sau:

Dòng đầu tiên và duy nhất của test case chứa hai số nguyên dương ~n~ và ~k~ (~3\le n\le 150\,000, 1\le k\le 150\,000~).

Dữ liệu đảm bảo tổng ~n~ và tổng ~k~ trong tất cả test case không vượt quá ~150\,000~.

Output

Với mỗi test case, in ra lần lượt ~k~ số nguyên ~f(n,n), f(n,n+1), \dots, f(n,n+k-1)~, modulo ~998\,244\,353~. Cụ thể, nếu đáp án được biểu diễn dưới dạng phân số tối giản ~\frac{p}{q}~, in ra số nguyên không âm ~s<998\,244\,353~ sao cho ~q\cdot s=p \pmod{998\,244\,353}~.

Scoring

Sample Input 1

2
3 4
4 7

Sample Output 1

887328314 0 813384288 271128096 
904658945 764280833 735035393 537628673 550423553 364897793 394485953

Notes

Với ~n=3~ và ~m=3~, dãy duy nhất có thể được tạo ra và thỏa mãn điều kiện đề bài là ~\{1,1,1\}~. Xác suất tạo ra dãy này là ~\frac{6}{27}~. Do đó, ~f(3,3)=\frac{6}{27}~. Chương trình cần in ra ~887\,328\,314~ do ~887\,328\,314\times 27=6 \pmod{998\,244\,353}~.

Với ~n=3~ và ~m=4~, có thể tạo ra nhiều dãy khác nhau, nhưng không có dãy nào thỏa mãn các phần tử là độ dài ba cạnh của một tam giác. Do đó, ~f(3,4)=0~.

Với ~n=3~ và ~m=5~, có ba dãy thỏa mãn điều kiện đề bài là ~\{1,2,2\}~, ~\{2,1,2\}~ và ~\{2,2,1\}~. Xác suất tạo ra mỗi dãy đều bằng ~\frac{10}{81}~. Do đó, ~f(3,5)=3\times \frac{10}{81}=\frac{10}{27}~. Chương trình cần in ra ~813\,384\,288~ do ~813\,384\,288\times 27=10 \pmod{998\,244\,353}~.

Với ~n=3~ và ~m=6~, dãy duy nhất có thể được tạo ra và thỏa mãn điều kiện đề bài là ~\{2,2,2\}~. Xác suất tạo ra dãy này là ~\frac{10}{81}~. Do đó, ~f(3,6)=\frac{10}{81}~. Chương trình cần in ra ~271\,128\,096~ do ~271\,128\,096\times 81=10 \pmod{998\,244\,353}~.

Plinko là một trò chơi trong đó người chơi thả một quả bóng từ đỉnh của một bảng có nhiều chốt. Quả bóng rơi xuống, nảy qua lại, và cuối cùng đi tới một trong các ô ở phía dưới.

Trong bài này, thay vì một bảng có chốt, Alice được cho một mê cung bằng gỗ với ~n~ hàng và ~m~ cột. Mê cung được biểu diễn như một lưới gồm ~n \times m~ ô, với các hàng được đánh số từ ~0~ đến ~n - 1~, và các cột được đánh số từ ~0~ đến ~m - 1~. Ô ở hàng thứ ~i~ và cột thứ ~j~ được ký hiệu là ~(i,j)~.

Một số ô của mê cung là ô trống, còn các ô còn lại là các khối gỗ. Các ô trống trong mỗi hàng được mô tả bởi một số đoạn rời nhau.

Ở hàng thứ ~i~, có ~s_i~ đoạn trống. Đoạn trống thứ ~j~ của hàng ~i~ được mô tả bởi hai số nguyên ~l_{i,j}~ và ~r_{i,j}~, nghĩa là mọi ô ~(i,k)~ thỏa mãn ~l_{i,j} \leq k < r_{i,j}~ đều là ô trống. Tất cả các ô khác trong hàng ~i~ là khối gỗ. Các đoạn trống trong mỗi hàng thỏa mãn ~0 \leq l_{i,1} < r_{i,1} < l_{i,2} < r_{i,2} < \ldots < l_{i,s_i} < r_{i,s_i} \leq m~.

Khi một quả bóng được đặt vào ô trống ~(x,y)~, nó có thể di chuyển tới một trong các ô kề sau:

• ~(x+1,y)~, đi xuống;

• ~(x,y+1)~, đi sang phải;

• ~(x,y-1)~, đi sang trái.

Quả bóng chỉ được phép di chuyển tới ô trống. Nó không được phép đi lên.

Ta nói rằng ô ~(a,b)~ có thể đi tới ô ~(c,d)~ nếu tồn tại một dãy các bước đi hợp lệ bắt đầu từ ~(a,b)~ và kết thúc tại ~(c,d)~.

Bob hỏi Alice ~q~ câu hỏi. Trong mỗi câu hỏi, Alice được cho năm số nguyên ~a,b,c,l,r~. Một quả bóng được đặt tại ô ~(a,b)~, và Alice phải xác định có bao nhiêu ô ~(c,d)~ thỏa mãn ~l \leq d \leq r~ có thể đi tới từ ~(a,b)~.

Đảm bảo rằng ~a \leq c~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \leq 5 \cdot 10^5~, ~1 \leq m \leq 10^9)~ – số hàng và số cột của mê cung.

Mỗi trong ~n~ dòng tiếp theo mô tả một hàng của mê cung. Dòng thứ ~i~ (~0 \le i < n~) bắt đầu bằng một số nguyên ~s_i~ – số đoạn trống trong hàng thứ ~i~. Sau đó là ~2\cdot s_i~ số nguyên: ~l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \ldots, l_{i,s_i}, r_{i,s_i}~ (~0 \leq l_{i,1} < r_{i,1} < l_{i,2} < r_{i,2} < \ldots < l_{i,s_i} < r_{i,s_i} \leq m~).

~\quad~ Gọi ~z = \sum_{i=0}^{n-1} s_i~. Đảm bảo rằng ~1 \leq z \leq 5 \cdot 10^5~.

Dòng tiếp theo chứa một số nguyên ~q~ ~(1 \leq q \leq 5 \cdot 10^5)~ – số câu hỏi.

Mỗi trong ~q~ dòng tiếp theo chứa năm số nguyên ~a,b,c,l,r~ mô tả một câu hỏi: ~0 \leq a \leq c < n~, ~0 \leq b < m~, và ~0 \leq l \leq r < m~.

Output

Với mỗi câu hỏi, in ra một số nguyên: số ô ~(c,d)~ sao cho ~l \leq d \leq r~ và ~(c,d)~ có thể đi tới từ ~(a,b)~.

Scoring

Sample Input 1

3 12
1 0 10
2 0 4 6 10
3 0 2 4 6 8 10
5
0 5 2 0 11
0 5 2 0 3
0 5 2 4 7
0 5 2 8 11
1 1 2 0 11

Sample Output 1

4
2
0
2
2

Notes

Trong ví dụ, đoạn trống ở hàng ~0~ là ~[0,10)~. Các đoạn trống ở hàng ~1~ là ~[0,4)~ và ~[6,10)~. Các đoạn trống ở hàng ~2~ là ~[0,2)~, ~[4,6)~, và ~[8,10)~.

Nếu quả bóng bắt đầu từ ô ~(0,5)~, nó có thể đi tới hai đoạn ~[0,4)~ và ~[6,10)~ ở hàng ~1~. Từ đó, nó có thể đi tới hai đoạn ~[0,2)~ và ~[8,10)~ ở hàng ~2~.

Vì vậy, trong các cột từ ~0~ đến ~11~ ở hàng ~2~, chính xác có ~4~ ô có thể đi tới.