Một vương quốc giàu có, một lâu đài nguy nga và một vị vua tài ba,...... Là những gì mà quốc gia này không có.

Ở đây chỉ có những tiếng gào thét của những người dân vô tội. Tiếng khóc thương từ những người qua đường không dám bước vào. Và tiếng kêu bất lực của vị vua.

Đất nước Craftania là một vương quốc đã từng rất thịnh vượng.

Nhưng sự thịnh vượng của nó không đến từ những cánh đồng lúa vàng ươm hay những mỏ kim cương lấp lánh, mà đến từ đôi bàn tay. Người ta từng nói rằng, nếu Chúa Trời tạo ra thế giới trong bảy ngày, thì người dân Craftania đã dành bảy thế kỷ sau đó để mài giũa nó trở nên hoàn hảo. Từng viên gạch lát đường ở đây đều là một tác phẩm nghệ thuật, từng chiếc đèn đường là một kiệt tác điêu khắc, và bản thân lâu đài hoàng gia – "Cung Điện Hổ Phách" – từng được ví là kỳ quan thứ tám của nhân loại.

Nhưng giờ đây, "kỳ quan" ấy trông giống như bộ xương khô của một con quái vật khổng lồ đã chết rũ.

Vị vua đang ngồi trên ngai vàng gãy nát kia là KDA, người từng được xưng tụng là "Kiến Trúc Sư Vĩ Đại". Ông không già đi vì tuổi tác, mà khô héo đi vì sự hối hận. Da ông xám ngoét như màu vôi vữa, đôi mắt trũng sâu nhìn chằm chằm vào khoảng không vô định nơi đại sảnh.

Cơn ác mộng bắt đầu từ mười năm trước, xuất phát từ chính cái tên đầy kiêu hãnh của vương quốc: Craft – Chế tác.

Khi ấy, Craftania đã đạt đến đỉnh cao của sự giàu có. Không còn gì để chinh phục, sự no đủ sinh ra nỗi sợ hãi về sự lụi tàn. Vua KDA, trong cơn say của quyền lực và nỗi ám ảnh về sự vĩnh cửu, đã ra lệnh cho Hội Đồng Giả Kim Thuật thực hiện một dự án điên rồ: "Dự án Bất Hoại". Ông muốn biến cả vương quốc, từ con người đến cỏ cây, trở thành những thực thể vĩnh cửu, không bệnh tật, không lão hóa, cứng cáp như kim cương và rực rỡ như vàng ròng.

Họ đã thành công. Hoặc ít nhất, họ nghĩ là họ đã thành công.

Một làn sương màu đồng thau đã được thả ra từ đỉnh tháp cao nhất vào một buổi chiều định mệnh. Nó được hứa hẹn là "Hơi thở của Thần", thứ sẽ bao bọc người dân trong lớp vỏ bảo vệ vĩnh cửu. Nhưng làn sương ấy không mang lại sự bất tử như trong truyện cổ tích. Nó mang đến sự đông cứng.

Lớp sương ấy thấm vào da thịt, biến các tế bào sống thành một dạng vật chất lai tạp giữa thịt xương và kim loại lạnh lẽo.

Hãy nhìn ra quảng trường lớn, nơi từng diễn ra những lễ hội rộn ràng. Giờ đây, nó là một bãi tha ma của những bức tượng sống. Những người dân vô tội – người đang bán bánh mì, kẻ đang khiêu vũ, đứa trẻ đang chạy theo quả bóng – tất cả đều bị "hóa đá" ngay trong khoảnh khắc ấy. Nhưng bi kịch nằm ở chỗ: Họ vẫn còn sống.

Đó là lý do vì sao không ai dám bước vào Craftania. Bởi vì nếu lắng tai nghe kỹ, xuyên qua lớp vỏ kim loại lạnh lẽo của những bức tượng kia, bạn sẽ nghe thấy tiếng tim đập thoi thóp. Và khi gió lùa qua những khe hở của các khớp xương đã bị kim loại hóa, nó tạo ra những âm thanh rít lên, nghe như tiếng gào thét xé lòng.

"Cứu... tôi..."

"Nóng quá..."

"Mẹ ơi..."

Những âm thanh ấy không phát ra từ miệng, vì môi họ đã bị hàn kín bởi lớp đồng thau, mà nó vang vọng trong tâm trí của bất cứ ai bước chân qua cổng thành. Đó là tiếng vọng của hàng vạn linh hồn bị cầm tù trong chính cơ thể mình, bất tử nhưng đau đớn tột cùng.

Vua KDA là người duy nhất miễn nhiễm một phần với làn sương nhờ chiếc áo choàng cổ ngữ, nhưng đó lại là hình phạt tàn khốc nhất. Ông không bị hóa đá, để ông phải chứng kiến, phải lắng nghe, và phải sống sót giữa "tác phẩm" kinh hoàng nhất của mình.

Mỗi đêm, khi trăng lên cao, chiếu rọi xuống những mái nhà đã rỉ sét, vua KDA lại lê bước chân nặng nhọc đi qua những hành lang vắng lặng. Ông dừng lại trước bức tượng của Hoàng hậu, người đang dang tay che chở cho cô con gái nhỏ. Khuôn mặt bà toát lên vẻ kinh hoàng vĩnh cửu, đôi mắt làm bằng ngọc bích trừng trừng nhìn ông đầy oán trách.

Ông chạm tay vào má bà. Lạnh ngắt. Nhưng ông cảm nhận được một rung động nhẹ dưới ngón tay – mạch máu của bà vẫn đang chảy, bị giam cầm trong lớp vỏ bất hoại này.

"Ta xin lỗi..." KDA thì thầm, giọng nói khàn đặc như tiếng cọ xát của hai tảng đá. "Ta chỉ muốn... chúng ta bên nhau mãi mãi."

Đáp lại ông chỉ là tiếng gió hú qua những tháp canh gãy nát, nghe như tiếng cười nhạo báng của số phận. Vương quốc Craftania vẫn ở đó, đúng như ước nguyện của ông: Giàu có (vì mọi thứ đều biến thành bán kim loại quý), nguy nga (vì không thời gian nào tàn phá được nữa), và vĩnh cửu.

...Vương quốc Craftania vẫn ở đó, đúng như ước nguyện của ông: Giàu có, nguy nga và vĩnh cửu.

50 năm sau sự kiện thảm hoạ đó, nhóm thám hiểm của bạn đã đặt chân đến vùng đất chết này, mang theo hy vọng giải mã lời nguyền và khôi phục sự sống.

Tại cổng thành rỉ sét, một sinh vật to lớn chặn đường các bạn. Đó là một con Orc Cổ Đại, kẻ tự xưng là "Thủ Hộ Giả Tri Thức". Đôi mắt hắn không có lòng đen, mà chạy dọc những dòng ký tự xanh biếc như một cỗ máy.

Hắn gầm gừ, giọng nói vang vọng như tiếng kim loại va đập:

Ta sở hữu trí tuệ tối thượng của những cỗ máy cổ xưa. Tư duy của ta là tuyệt đối, là khuôn khổ của vũ trụ này. Các ngươi là những sinh vật hữu hạn, làm sao hiểu được vẻ đẹp của những con số?

Hắn đưa ra một thách thức:

Trong thế giới của ta, có một ranh giới nơi mà 'cực đại' gặp gỡ 'vực thẳm'. Nếu các ngươi có thể cho ta thấy một phép tính vi phạm lẽ thường của con người, nhưng lại tuân theo quy luật 'vòng lặp' trong trí tuệ của ta, ta sẽ để các ngươi đi qua.

Nhà hiền triết trong đoàn ghé tai bạn thì thầm: "Hắn tư duy như một cỗ máy tính toán có giới hạn. Hắn tin rằng khi đi đến tận cùng của đỉnh cao, ta sẽ rơi xuống đáy sâu nhất. Hãy cho hắn thấy nghịch lý đó."

Hãy tìm ra phép tính để đánh lừa "trí tuệ máy tính" của hắn.

Input

Bài này không có input.

Output

In ra trên 1 dòng là phép tính thoả yêu cầu trên với định dạng như sau:

a x b = c

Với:

• a là số thứ nhất.
• x là một trong bốn phép tính số học (+, -, *, /).
• b là số thứ hai.
• = là dấu bằng (bắt buộc).
• c là số thứ ba.

Tất cả đều là số nguyên có dấu 32 bit và các dấu cách phải đúng với định dạng đã đưa.

Sau khi đánh lừa được tên Orc Cổ Đại, cánh cổng thành nặng nề rên rỉ mở ra. Trước mắt các bạn không phải là một con đường rộng mở, mà là một hành lang dài hun hút, tối tăm và lạnh lẽo, dẫn thẳng vào trung tâm Cung Điện Hổ Phách.

Hai bên vách tường của hành lang này được khảm một dãy những hốc đèn làm bằng pha lê đen, tổng cộng có ~N~ hốc đèn được đánh số từ 1 đến ~N~.

Theo những ghi chép cổ xưa của nhà hiền triết, đây là hệ thống phòng thủ "Tiếng Thét Hư Không". Những chiếc đèn này không cháy bằng lửa, mà bằng năng lượng linh hồn. Tuy nhiên, hệ thống này có một quy tắc chết người về sự ổn định:

"Ánh sáng không được chạm vào ánh sáng. Nếu hai hốc đèn liền kề nhau cùng được thắp sáng, sự cộng hưởng năng lượng sẽ tạo ra một tiếng thét sóng âm khủng khiếp, phá nát màng nhĩ của bất kỳ ai đang đứng trong hành lang và chôn vùi họ dưới đống đổ nát."

Khi các bạn bước vào, các bạn nhận thấy tại hốc đèn thứ ~p~, ngọn lửa linh hồn đang cháy rực rỡ. Nó dường như là ngọn đèn vĩnh cửu dẫn lối, không thể bị dập tắt.

Để đi qua hành lang an toàn, các bạn cần kích hoạt hệ thống đèn để soi sáng đường đi, nhưng tuyệt đối không được kích hoạt bẫy âm thanh. Nhà hiền triết cần tính toán xem có tất cả bao nhiêu cách thiết lập trạng thái (Sáng/Tắt) cho toàn bộ ~N~ hốc đèn, biết rằng hốc đèn thứ ~p~ bắt buộc phải Sáng, và không có bất kỳ hai hốc đèn Sáng nào nằm cạnh nhau.

Hãy giúp nhà hiền triết tính toán con số này để mở khóa cơ chế an toàn của hành lang.

Input

Dòng đầu tiên chứa số nguyên ~T \left(1 \leq T \leq 2 \times 10^4 \right)~ là số test case. ~T~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên:

• ~N \left(1 \leq N \leq 45 \right)~ là số hốc đèn.
• ~p \left(1 \leq p \leq N \right)~ là vị trí đèn bắt buộc Sáng.

Đề đảm bảo tổng các N của mỗi test case sẽ ~\leq 2 \times 10^5~

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả của phép chia lấy dư của các cách thiết lập trạng thái với ~10^9 + 7~.

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

13
3
42
2
4
1

Note

Ví dụ với test case thứ 5, các cách thiết lập hợp lệ là:

• 00100,
• 00101,
• 10100,
• 10101.

Vượt qua hành lang ánh sáng, nhóm thám hiểm cuối cùng cũng bước vào Đại Sảnh Đường, nơi ngai vàng của vua KDA ngự trị.

Không gian ở đây đặc quánh lại, không khí rung lên bần bật theo từng đợt sóng vô hình. Ở giữa sảnh, lơ lửng ngay trên ngai vàng, là một khối tinh thể khổng lồ đang đập từng nhịp thong thả nhưng nặng nề. Đó là "Trái Tim Hổ Phách" - nguồn năng lượng duy trì sự "bất tử" cho cả vương quốc này.

Nhà hiền triết nhận ra rằng, để phá giải lời nguyền, họ không thể đập vỡ trái tim (vì sẽ khiến cả vương quốc sụp đổ), mà phải hòa nhịp với nó để tháo gỡ các phong ấn thời gian.

Trái tim này hoạt động theo một quy luật dao động năng lượng cổ xưa gọi là "Tam Giác Hư Không":

• Nhịp đập đầu tiên phát ra mức năng lượng là ~a~.
• Nhịp đập thứ hai phát ra mức năng lượng là ~b~.
• Từ nhịp đập thứ 3 trở đi, mức năng lượng sinh ra là sự giao thoa (phép XOR) của hai nhịp đập ngay trước nó.

Nói cách khác, nếu gọi ~F[i]~ là mức năng lượng tại nhịp thứ ~i~, ta có:

~ \begin{align} F[1] &= a \\ F[2] &= b \\ F[3] &= a \oplus b \end{align} ~

Để thực hiện nghi thức giải nguyền tại một thời điểm ~N~ (tức là tại nhịp đập thứ ~N~), các bạn cần phải biết được tính "ổn định" của dòng năng lượng đó. Cụ thể, các bạn cần đếm xem trong quá khứ, từ nhịp đầu tiên cho đến nhịp hiện tại (từ ~1~ đến ~N~), đã có bao nhiêu lần mức năng lượng giống hệt với mức năng lượng tại thời điểm ~N~ xuất hiện.

Vì "Trái Tim Hổ Phách" đã đập từ hàng ngàn năm nay, số ~N~ có thể vô cùng lớn. Hãy giúp nhà hiền triết trả lời các truy vấn này thật nhanh chóng.

Input

Dòng đầu tiên chứa 3 số nguyên ~a~, ~b~ là hai mức năng lượng khởi đầu và ~T~ là số lần cần kiểm tra (~0 < a, b \le 10^{18}, 1 \le T \le 10^5~). ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~ (~1 \le N \le 10^{18}~).

Output

In ra ~T~ dòng, mỗi dòng là một số nguyên duy nhất là số lượng vị trí ~i~ (~1 \le i \le N~) sao cho ~F[i] = F[N]~.

3 4 2
1
4

1
2

Sau khi hòa nhịp được với "Trái Tim Hổ Phách", các phong ấn bảo vệ Cung Điện Hổ Phách dần được gỡ bỏ. Tuy nhiên, lối lên ngai vàng của vua KDA – đỉnh tháp cao nhất "The Zenith" – đã bị vỡ vụn thành hàng ngàn mảnh lơ lửng trong không trung.

Không gian tại đây bị bẻ cong, các quy tắc vật lý thông thường không còn áp dụng. Để di chuyển, các bạn tìm thấy một bảo vật do chính tay nhà vua chế tác năm xưa: Khối Lập Phương Hư Không.

Khu vực này được mô tả như một bản đồ các mảnh vỡ không gian gồm ~N~ mảnh (đánh số từ ~1~ đến ~N~). Vị trí hiện tại của các bạn là mảnh số ~1~, và đích đến là ngai vàng tại mảnh số ~N~. Các mảnh vỡ được kết nối với nhau bởi ~M~ luồng năng lượng. Khoảng cách giữa hai mảnh vỡ bất kỳ được tính bằng số bước ngắn nhất đi theo các luồng năng lượng này.

Khối Lập Phương Hư Không hoạt động theo cơ chế rủi ro nhưng đầy quyền năng:

1. Nạp năng lượng: Mỗi lần muốn di chuyển, bạn phải kích hoạt khối lập phương. Nó có ~K~ mức năng lượng từ ~1~ đến ~K~. Xác suất để khối lập phương đạt mức năng lượng ~x~ là ~P_x~.
2. Ổn định không gian: Tuy nhiên, năng lượng không gian rất bất ổn. Nếu khối lập phương đạt mức năng lượng là ~x~, thực tế nó sẽ chỉ cho phép bạn thực hiện bước nhảy với khoảng cách ~y~ (~1 \le y \le x~) với một xác suất là ~G_{x, y}~.
3. Chọn điểm đến: Khi khoảng cách nhảy ~y~ đã được ấn định bởi vũ trụ, bạn có quyền năng tự chọn điểm đến tiếp theo là bất kỳ mảnh vỡ nào cách vị trí hiện tại đúng một khoảng bằng ~y~.

Quy Tắc "Lực Hút Ngai Vàng": Nếu khoảng cách nhảy ~y~ đủ lớn để bạn chạm tới hoặc vượt qua ngai vàng (khoảng cách từ chỗ đứng đến đích ~\le y~), bạn sẽ ngay lập tức được dịch chuyển thẳng đến ngai vàng và kết thúc hành trình.

Vì vua KDA sắp trở nên hoá điên nên thời gian không còn nhiều, Nhà hiền triết muốn tính toán chiến thuật di chuyển tối ưu để số lần kích hoạt Khối Lập Phương trung bình là thấp nhất.

Input

Dòng đầu tiên chứa ~1~ số nguyên dương ~T~ (~T \le 10~) là số lượng tình huống giả lập ta cần xử lý.

Trong mỗi tình huống có:

• Dòng đầu tiên chứa ~3~ số nguyên dương ~N, M, K~ ~(N \le 10^5, M \le 5 \cdot 10^5, K \le 100)~.
• Dòng tiếp theo chứa ~K~ số nguyên ~P'_1, P'_2, \dots, P'_K~ ~(1 \le P'_i \le 100, \sum_{i = 1}^K P'_i = 100, 100 * P_i = P'_i)~.
• ~K~ dòng tiếp theo được đánh số từ ~1~ đến ~K~, dòng thứ ~i~ chứa ~i~ số nguyên không âm ~G'_{i, 1}, G'_{2, i}, \dots, G'_{i, i}~ ~(0 \le G'_{i, x} \le 100, \sum_{j = 1}^K G'_{i, j} = 100, 100 * G_{i, x} = G'_{i, x})~.
• Trong mỗi dòng của ~M~ dòng tiếp theo chứa ~2~ số nguyên dương ~u, v~ là ~2~ mảnh vỡ được kết nối với nhau bởi ~1~ luồng năng lượng ~(u, v \le N)~.

* Lưu ý: Đề đảm bảo tổng số mảnh vỡ ~N~ không vượt quá ~10^5~ cũng như tổng số luồng năng lượng ~M~ không vượt quá ~5 \cdot 10^5~ trong tất cả các tình huống.

Output

Với mỗi tình huống, in ra trên một dòng là một số thực ~D~ là đáp án của đó tình huống đó (đáp án được coi là đúng nếu sai số không quá ~10^{-6}~).

In ra ~D = 0~ trong trường hợp bạn không đến được mảnh vỡ thứ ~N~.

2
4 3 3
20 30 50
100
0 100
0 0 100
1 2
2 3
3 4
5 5 10
10 10 10 10 10 10 10 10 10 10
100
10 90
10 10 80
10 10 10 70
10 10 10 10 60
10 10 10 10 10 50
10 10 10 10 10 10 40
10 10 10 10 10 10 10 30
10 10 10 10 10 10 10 10 20
10 10 10 10 10 10 10 10 10 10
1 2
1 3
1 4
1 5
4 5

1.5400000000
1.0000000000

Đề không văn

Cho ~1~ đồ thị ~G = (V, E)~ với ~N = |V|~ và ~M = |E|~. Các đỉnh trong đồ thị được đánh số từ ~1~ đến ~N~. Cho thêm ~1~ xúc xắc có ~K~ mặt được đánh số bằng số nút, và mỗi mặt ~x~ có xác xuất tung là ~P_x~. Gọi ~d(x, y)~ là hàm tính khoảng cách ngắn nhất đi từ đỉnh ~x~ đến đỉnh ~y~ tình bằng cạnh.

Hiện tại ta đang ở đỉnh ~1~ của đồ thị và đang tìm cách đến đỉnh ~N~, nhưng để làm được thì trước khi di chuyển ta phải tung xúc xắc. Giả sử đỉnh ta đang ở là ~s~, thì khi tung ra mặt ~x~ của xúc xắc, ta có thể đến ~1~ trong số những đỉnh ~t~ thỏa ~d(s, t) \le x~. Đặc biệt, ta có ~G_{x, y}~ phần trăm khả năng chọn đến ~1~ trong những đỉnh ~t~ thỏa ~d(s, t) = y~ (tất nhiên ~y \le x~) khi tung được số nút là ~x~. Ta sẽ lặp lại bước tung xúc xắc, chọn đỉnh muốn đến tại mỗi lượt di chuyển cho đến khi đến được đỉnh ~N~. Đặc biệt nếu ta chọn nhảy khoảng cách ~y~ mà ta đã có thể đến đỉnh ~N~ với khoảng cách ngắn hơn thì ta được mặc định là đã đến đỉnh ~N~.

Yêu cầu: Tìm số lượt trung bình ít nhất ta cần để di chuyển từ đỉnh ~1~ đến ~N~.

Input

Dòng đầu tiên chứa ~1~ số nguyên dương ~T~ (~T \le 10~) là số testcase ta phải xử lý.

Trong mỗi testcase có:

• Dòng đầu tiên chứa ~3~ số nguyên dương ~N, M, K~ ~(N \le 10^5, M \le 5 \cdot 10^5, K \le 100)~.

• Dòng tiếp theo chứa ~K~ số nguyên ~P'_1, P'_2, \dots, P'_K~ ~(1 \le P'_i \le 100, \sum_{i = 1}^K P'_i = 100, 100 * P_i = P'_i)~.

• ~K~ dòng tiếp theo được đánh số từ ~1~ đến ~K~, dòng thứ ~i~ chứa ~i~ số nguyên không âm ~G'_{i, 1}, G'_{2, i}, \dots, G'_{i, i}~ ~(0 \le G'_{i, x} \le 100, \sum_{j = 1}^K G'_{i, j} = 100, 100 * G_{i, x} = G'_{i, x})~.

• Trong mỗi dòng của ~M~ dòng tiếp theo chứa ~2~ số nguyên dương ~u, v~ là ~2~ đỉnh của ~1~ cạnh trong đồ thị ~(u, v \le N)~.

* Lưu ý: Đề đảm bảo tổng số đỉnh ~N~ không vượt quá ~10^5~ cũng như tổng số cạnh ~M~ không vượt quá ~5 \cdot 10^5~ trong tất cả các testcase.

Output

Với mỗi testcase, in ra trên ~1~ dòng là ~1~ số thực ~D~ là đáp án của testcase đó (đáp án được coi là đúng nếu sai số không quá ~10^{-6}~).

Sample Input 1

2
4 3 3
20 30 50
100
0 100
0 0 100
1 2
2 3
3 4
5 5 10
10 10 10 10 10 10 10 10 10 10
100
10 90
10 10 80
10 10 10 70
10 10 10 10 60
10 10 10 10 10 50
10 10 10 10 10 10 40
10 10 10 10 10 10 10 30
10 10 10 10 10 10 10 10 20
10 10 10 10 10 10 10 10 10 10
1 2
1 3
1 4
1 5
4 5

Sample Output 1

1.5400000000
1.0000000000

Sau khi vượt qua không gian phân mảnh, nhóm thám hiểm đứng trước cánh cổng khổng lồ dẫn vào Tẩm Cung Hổ Phách – nơi Vua KDA đang ẩn mình.

Nhưng lối vào đã bị chặn đứng bởi Đội Cấm Vệ Quân. Đó không phải là người bằng xương bằng thịt, mà là ~n~ bộ giáp rỗng ruột bằng đồng thau, đứng sừng sững trên ~n~ bệ đá xếp thành một vòng tròn khép kín bao quanh tẩm cung. Các bệ đá được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ.

Trên tay mỗi bộ giáp cầm một thanh đại kiếm. Cơ chế bảo vệ này được gọi là "Vòng Xoay Tử Thần". Để mở cánh cổng, các bạn không được phá hủy chúng (vì chúng sẽ tự tái tạo), mà phải hack vào hệ thống điều khiển để khiến chúng tự khóa lẫn nhau.

Hệ thống điều khiển bao gồm ~n~ "Lõi Năng Lượng" bị tháo rời, mỗi lõi chứa một giá trị dịch chuyển ~d_i~. Nhà vua điên loạn đã thiết kế hệ thống sao cho:

1. Bạn phải nạp mỗi bệ đá (vị trí ban đầu ~j~) một lõi năng lượng ~d_k~ bất kỳ trong số các lõi thu được.
2. Khi hệ thống kích hoạt, bộ giáp tại vị trí ~j~ nhận lõi có giá trị ~d~ sẽ lập tức di chuyển theo chiều kim đồng hồ đúng ~d~ bước để đến bệ đá mới.
   • Ví dụ: Nếu ~n=5~, đứng ở bệ 2, lắp lõi ~d = 4~: Di chuyển qua 3, 4, 5, và dừng lại ở 1.

Cánh cổng chỉ mở ra khi hệ thống đạt trạng thái "Cân Bằng Tuyệt Đối": Sau khi tất cả ~n~ bộ giáp di chuyển đồng thời, mỗi bệ đá phải có đúng một bộ giáp trấn giữ. Nếu có bất kỳ bệ đá nào bị bỏ trống (hoặc có 2 bộ giáp va vào nhau tại cùng một bệ), hệ thống phòng thủ sẽ kích hoạt tia lazer tiêu diệt tất cả những kẻ xâm nhập.

Trong tay các bạn đang là ~n~ lõi năng lượng với các giá trị ~d_1, d_2, \dots, d_n~. Hãy tìm cách lắp chúng vào ~n~ bệ đá ban đầu sao cho trạng thái cân bằng được thiết lập, mở đường vào gặp nhà vua.

Input

Dòng đầu tiên chứa một số nguyên ~T~ (~1 \leq T \leq 1000~) - số lượng test.

Với mỗi test có định dạng:

• Dòng thứ nhất chứa một số nguyên ~n~ (~1 \leq n \leq 100~) - số lượng bộ giáp.
• Dòng thứ hai chứa ~n~ số nguyên ~d_1, d_2, \ldots, d_n~ (~1 \leq d_i \leq n~) - giá trị của các lõi năng lượng thu được.

Output

Với mỗi test, in ra kết quả tương ứng:

• Nếu không thể thiết lập trạng thái cân bằng, in ra một dòng duy nhất chứa NO.
• Nếu tồn tại cách thiết lập:
  • Dòng đầu tiên in YES.
  • Dòng thứ hai, in ra ~n~ số nguyên ~A_1, A_2, \ldots, A_n~, trong đó ~A_j~ là giá trị của lõi năng lượng được lắp vào bệ đá thứ ~j~. Dãy số ~A~ này phải là một hoán vị của dãy ~d~ đã cho.

Nếu có nhiều cách thiết lập, bạn chỉ cần in ra một cách bất kỳ.

Scoring

Example

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

YES
1 1 1 1
NO
YES
4 1 1 2 2

Note

Giải thích cho ví dụ 3 (~N=5~, với các lõi cho trước là ~\{1, 1, 2, 2, 4\}~):

Cách lắp đặt: Bệ 1 lắp lõi 4, Bệ 2 lắp lõi 1, Bệ 3 lắp lõi 1, Bệ 4 lắp lõi 2, Bệ 5 lắp lõi 2.

• Bộ giáp tại Bệ 1 (lõi ~4~): đi qua 2, 3, 4, 5 ~\rightarrow~ Dừng tại Bệ 5.
• Bộ giáp tại Bệ 2 (lõi ~1~): đi qua 3 ~\rightarrow~ Dừng tại Bệ 3.
• Bộ giáp tại Bệ 3 (lõi ~1~): đi qua 4 ~\rightarrow~ Dừng tại Bệ 4.
• Bộ giáp tại Bệ 4 (lõi ~2~): đi qua 5, 1 ~\rightarrow~ Dừng tại Bệ 1.
• Bộ giáp tại Bệ 5 (lõi ~2~): đi qua 1, 2 ~\rightarrow~ Dừng tại Bệ 2.

Kết quả: Các vị trí đích là ~\{5, 3, 4, 1, 2\}~. Mỗi bệ đá đều có đúng 1 bộ giáp. Cửa mở!

Thông báo quan trọng

Server của bài này đã bị tắt vì tác giả không thể chạy 24/24 được. Các bạn muốn giải bài này chỉ cần in ra CRAFTANIA{YOU_SAVED_ME}

Cánh cổng Tẩm Cung Hổ Phách ầm ầm mở ra. Nhưng thứ đón chờ các bạn không phải là vàng son lộng lẫy, cũng không phải là bóng tối u ám.

Thứ các bạn nhìn thấy là... Hư Vô (The Void).

Sàn nhà dưới chân các bạn bắt đầu rung chuyển dữ dội. Những bức tường đá cẩm thạch kiên cố của lâu đài bỗng chốc nhấp nháy, xuất hiện những sọc màu nhiễu loạn (glitch) xanh đỏ. Trần nhà cao vút kia đang bong tróc từng mảng lớn, nhưng không rơi xuống đất mà bay ngược lên trời, để lộ ra những khung lưới (wireframe) màu đen kịt của cấu trúc không gian.

Ở chính giữa sự hỗn mang đó, Vua KDA đang lơ lửng trên một ngai vàng được tạo thành từ hàng ngàn dòng lệnh (code) đang chạy điên cuồng. Cơ thể ngài không còn hình dạng con người nữa. Một nửa khuôn mặt ngài là vẻ uy nghiêm của một vị vua già, nửa còn lại là những khối vuông Pixelated đang phân rã và tái tạo liên tục.

Tiếng nói của ngài vang lên, không phải từ không trung, mà nó chèn trực tiếp vào đại não của các bạn, âm thanh rè rè như tiếng ổ cứng bị hỏng:

"Chào mừng đến với Kernel của thế giới này. Ta đã đợi các ngươi, những Debugger nhỏ bé."

Ngài giơ bàn tay đang phân rã của mình lên, nắm lấy một khoảng không. Không gian xung quanh vặn xoắn lại.

"Các ngươi nhìn xem, thế giới ngoài kia thật thảm hại làm sao. Con người sinh ra, già đi, bệnh tật và chết. Cảm xúc thì hỗn loạn, tư duy thì phi logic. Đó là một chương trình thất bại! Một đống 'Spaghetti Code' không thể cứu vãn!"

Một luồng sáng tím bùng lên từ ngực trái của nhà vua – nơi đáng lẽ là trái tim, giờ đây là một Khối Lệnh (Command Block) đang đập thình thịch.

"Ta đã tìm ra giải pháp. Nếu không thể sửa lỗi (fix bug) thế giới cũ, ta sẽ viết đè lên nó (overwrite). Ta sẽ đưa tất cả về dạng nguyên thủy nhất, hoàn hảo nhất. Nơi mọi thứ đều là những khối vuông. Nơi 1 mét là 1 khối. Nơi mặt trời mọc và lặn theo chu kỳ Tick chính xác tuyệt đối. Nơi không có đau khổ, chỉ có những dòng lệnh tuân thủ tuyệt đối!"

"HỆ THỐNG CẢNH BÁO: PHÁT HIỆN CAN THIỆP KHÔNG GIAN CẤP ĐỘ ADMIN."

"Hãy chứng kiến kỷ nguyên mới! Kỷ nguyên của MINECRAFT: OVERWRITE!"

Vua KDA gõ mạnh cây trượng xuống hư không. Một dòng lệnh khổng lồ hiện ra, xé toạc bầu trời:

/execute at @e run particle minecraft:explosion ~ ~ ~ 10 10 10 1 1000

Thế giới tối sầm lại. Khi các bạn mở mắt ra, các bạn thấy đôi tay mình đã trở thành hình khối. Thanh máu (Health Bar) và Thanh thức ăn (Hunger Bar) hiện lên góc màn hình. Xung quanh các bạn là một đấu trường khổng lồ lơ lửng giữa trời xanh và biển dung nham.

Trước mặt các bạn, Vua KDA đã triệu hồi 10 boss canh cửa đáng sợ, xung quanh được bao bọc bởi những chiếc khiên Barrier Block tàng hình.

Nhiệm vụ của "Người Được Chọn"

Đây là thử thách cuối cùng. Không còn trình biên dịch (Compiler), không còn IDE, không còn test case. Vũ khí duy nhất của các bạn là kỹ năng sinh tồn và khả năng phối hợp đồng đội.

Bạn phải đăng nhập vào thế giới ảo do Vua KDA tạo ra và đánh bại hắn để giành lấy quyền kiểm soát (Root Access), ngăn chặn quá trình ghi đè thực tại.

Hướng dẫn kết nối đến "Chiến Trường Ảo":

• Client: Sử dụng Minecraft Java Edition phiên bản 1.21.8 (Bắt buộc).
• Server IP: minecraft.lhpoj.io.vn (Sẽ được BTC mở vào giờ G).
• Tài khoản: Đăng nhập vào Server với cú pháp /register <mật khẩu>.
• Vào lúc 21 giờ 30, sẽ có boss xuất hiện.

Lời khuyên từ Nhà Hiền Triết

"Đừng bao giờ đi một mình. Trong thế giới của những khối vuông, sức mạnh của tình bạn (và kim cương) là thứ duy nhất phá vỡ được mọi thuật toán. Hãy nhớ, hắn là một Admin, nhưng hắn cũng tuân theo quy tắc của Game. Tìm điểm yếu trong hitbox của hắn!"