Cách mạng Tháng Tám năm 1945 là một trong những mốc son chói lọi nhất trong lịch sử dân tộc ta. Dưới sự lãnh đạo của Đảng và Chủ tịch Hồ Chí Minh, nhân dân Việt Nam đã vùng lên giành chính quyền, khai sinh ra nước Việt Nam Dân chủ Cộng hòa – mở ra kỷ nguyên độc lập, tự do cho dân tộc.

80 năm đã qua, tinh thần Cách mạng Tháng Tám vẫn là ngọn lửa bất diệt, hun đúc ý chí kiên cường và khát vọng vươn lên của các thế hệ người Việt Nam hôm nay và mai sau.

Hôm nay, Phong, nhân vật chính của chúng ta, quyết định tìm hiểu về sự kiện ý nghĩa này. Dưới không khí náo nức, những con đường tràn ngập cờ hoa rực rỡ, Phong cặm cụi lật mở từng trang sách, lướt qua trang web lịch sử, đọc từng dòng thông tin quý báu.

Sau một lúc miệt mài với đống tài liệu, Phong chợt tìm thấy phía sau một cuốn sách có một biểu tượng kì lạ, nhưng vô cùng tinh xảo. Bên dưới biểu tượng có ghi dòng chữ mờ mà Phong đọc không rõ. Do tò mò, Phong thử đặt tay lên biểu tượng đó, bất chợt, một ánh vàng lấp lánh lóe lên, bao trùm không gian xung quanh Phong. Chưa kịp hiểu chuyện gì vừa xảy ra, vầng sáng ấy bỗng xoáy lại, hút Phong vào bên trong, như thể có một cánh cửa vừa mở ra giữa hư không vậy.

Lúc mở mắt ra, Phong thấy trước mặt mình không còn là căn phòng quen thuộc của mình. Thay vào đó là một gian nhà tranh nhỏ, với ánh đèn dầu mập mờ, và vài âm thanh côn trùng trong khu rừng sâu tối tăm. Ngay lúc đấy, có một cán bộ trung niên bước ra và bảo:

~-~ Cuối cùng cậu cũng đến rồi. Vào đây tôi bảo cái này.

Sau một hồi quan sát, cuối cùng Phong cũng nhận ra mình đã được đưa về quá khứ, thời điểm chuẩn bị cho cuộc Cách mạng tháng Tám.

Đêm hôm ấy, Phong được giao nhiệm vụ quan sát các hoạt động giao liên của địch, bám sát nhất cử nhất động của đối phương, tìm hiểu cách họ liên lạc với nhau. Được biết đây là một nhiệm vụ then chốt, có thể ảnh hưởng đến kết quả của chiến dịch, Phong vô cùng cẩn trọng.

Phong cùng đồng đội len lỏi, bước đi trên con đường sỏi đá gập ghềnh, dưới ánh trăng rạng ngời dẫn lối, họ đã đến được vị trí quan sát. Không gian xung quanh lạnh buốt, thêm tiếng gió rít bên tai khiến Phong rợn tóc gáy, nhưng với lòng dũng cảm, anh trấn tĩnh bản thân và chuẩn bị ghi chép. Lúc này, Phong tự nhủ: "Đã đến được đây thì mình phải cố gắng hết sức để hoàn thành nhiệm vụ này".

Sau một vài ngày đêm quan sát, Phong biết được rằng căn cứ của địch gồm ~N~ chốt. Để liên lạc từ chốt ~a~ đến chốt ~b~, họ nối đường dây điện thoại một chiều từ ~a~ đến ~b~. Ngoài ra, Phong còn đánh cắp được bảng thông tin về điện thoại của ~N~ chốt. Dựa vào đây, anh và cán bộ chỉ huy biết được chốt thứ ~i~ có thể gọi cho ~a_i~ chốt và có thể nhận cuộc gọi từ ~b_i~ chốt, nhưng lại không biết cụ thể là chốt nào vì thông tin đã được mã hóa.

Một điều nữa khiến cán bộ thắc mắc là ở một số chốt ~j~, kí hiệu của chốt đó cũng xuất hiện trong danh sách cuộc gọi đi và đến của chốt đó. Phong giải thích điều này có nghĩa là ngoài giao tiếp bằng điện thoại, chốt đó còn có một giao liên, anh ta sẽ xuất phát tại chốt ~j~, làm nhiệm vụ được giao và quay trở lại chốt.

Sau khi trình bày toàn bộ cho cán bộ, mắt ông sáng bừng lên, khen Phong làm việc rất tốt. Rồi ông nhờ Phong cùng với những người đồng đội, hãy thử vẽ đồ thị mô tả liên lạc giữa ~N~ chốt đó, bao gồm cả những người giao liên (nếu có). Do cán bộ đã giữ bản chính, nên Phong không biết chốt nào có giao liên, nhưng Phong biết được rằng:

• Chỉ có tối đa một giao liên ở mỗi chốt.

• Giữa hai chốt ~a~ và ~b~ thì có tối đa một đường dây điện thoại từ ~a~ sang ~b~, và tối đa một đường dây điện thoại từ ~b~ sang ~a~.

Bây giờ bạn đã gia nhập đội của Phong, hãy giúp Phong tìm ra một đồ thị bất kì thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ là số chốt trong căn cứ của địch.

• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, \dots, a_n~ (~0 \leq a_i \leq 5 \times 10^5~), trong đó ~a_i~ cho biết số chốt mà từ chốt ~i~ có thể thực hiện cuộc gọi (tính cả giao liên của chốt ~i~ nếu có).

• Dòng thứ ba chứa ~N~ số nguyên ~b_1, b_2, b_3, \dots, b_n~ (~0 \leq b_i \leq 5 \times 10^5~), trong đó ~b_i~ cho biết số chốt mà có thể thực hiện cuộc gọi đến chốt ~i~ (tính cả giao liên của chốt ~i~ nếu có).

Output

Nếu không thể tìm ra đồ thị thỏa mãn yêu cầu, in ra ~-1~. Ngược lại, in ra mô tả đồ thị mà Phong cần tìm như sau:

• Dòng đầu tiên chứa một số nguyên ~M~ (với ~1 \leq M \leq 10^6~) là số đường dây điện thoại tìm được (tính cả giao liên).

• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ (~1 \leq u_i, v_i \leq n~), thể hiện một đường dây điện thoại ~u_i \rightarrow v_i~ nếu ~u_i \neq v_i~, hoặc thể hiện giao liên của chốt ~u_i~ nếu ~u_i = v_i~.

Scoring

Sample Input 1

3
1 1 1
1 1 1

Sample Output 1

3
3 1
2 2
1 3

Sample Input 2

3
3 2 1
2 1 3

Sample Output 2

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

Notes

Với ví dụ đầu tiên, từ thông tin mà Phong nhận được ta thấy tất cả các chốt đều có ~1~ đường dây đi và ~1~ đường dây đến. Một đồ thị mà Phong có thể đưa ra gồm ~3~ đường dây là:

• Một đường dây điện thoại nối chốt ~3 \rightarrow 1~.

• Một giao liên của chốt ~2~.

• Một đường dây điện thoại nối chốt ~1 \rightarrow 3~.

Sau khi thu thập được một số thông tin về cách liên lạc của đối phương, Phong đã được tin tưởng hơn. Vào một buổi tối, Phong được triệu tập đến một cái lán nhỏ nằm sâu trong rừng rậm. Cái lán dã chiến đơn sơ, được lợp bằng lá, bên trong là chiếc bàn tre cùng vài cái ghế con. Bầu không khí vô cùng nghiêm trang được soi rọi bởi ánh đèn dầu le lói, nhiều gương mặt gầy gò, ánh mắt nghiêm nghị đang chăm chăm nhìn vào tấm bản đồ sờn cũ bạc màu. Họ là những lãnh đạo, đóng vai trò then chốt quyết định vận mệnh của cả dân tộc.

Phong bước đến, chọn một cái ghế và ngồi xuống. Mọi người trong cái lán ấy đều biết rõ, thời cơ đang đến gần, bởi quân Pháp đã suy yếu, còn quân Nhật đang hoang mang. Tuy nhiên, việc đánh ở đâu, đánh thế nào, khi nào mới là quan trọng, bởi chọn lựa sai bây giờ, biết bao sinh mạng sẽ uổng phí, và cơ hội lịch sử có thể trôi qua.

Phong ngồi lặng ở một góc, quan sát từng khuôn mặt. Cậu hiểu rằng sức mạnh lớn nhất của cách mạng năm 1945 không nằm ở súng ống, mà ở quần chúng nhân dân – những người nông dân áo vải, công nhân, thanh niên, phụ nữ... tất cả cùng khát khao độc lập. Trong đầu Phong vang lên những dòng sách sử từng đọc, giờ đây như sống động ngay trước mắt: hàng vạn người xuống đường, cờ đỏ sao vàng rợp trời, tiếng hô vang át mọi nỗi sợ.

Một cán bộ trẻ cuối cùng cất tiếng, giọng dứt khoát: thay vì tập trung vào đánh chiếm từng đồn bốt, cần huy động lực lượng quần chúng biểu tình, phối hợp mít tinh, tuần hành, giành chính quyền bằng sức mạnh áp đảo của nhân dân. Mỗi làng xã, mỗi đô thị đều phải là một ngọn lửa, cùng thổi bùng ngọn sóng tổng khởi nghĩa, khi đó sức mạnh của ta sẽ như một dòng thác lớn, không gì có thể cản nổi.

Ý tưởng ấy như một luồng gió mới. Các lãnh đạo gật gù, rồi cùng bàn bạc chi tiết: ai phụ trách huy động thanh niên, ai liên lạc với các đoàn thể, cách in truyền đơn, cách tổ chức mít tinh sao cho đông đảo mà vẫn an toàn. Không khí trong lán bỗng bừng lên, giống như một dòng chảy âm thầm đã tìm thấy hướng thoát ra.

Phong lặng lẽ quan sát, trong lòng dâng trào cảm xúc. Cậu cảm nhận được khoảnh khắc hàng triệu con người Việt Nam sung sướng khi thoát khỏi xiềng xích thực dân, không còn bị bóc lột, khi được sống dưới sự lãnh đạo của một Nhà nước vì nhân dân. Trước mắt cậu bây giờ là lúc mà khoảnh khắc ấy được thai nghén, không phải trong sách, mà là thực tại.

Đến đây, trong tiếng giò xào xạc, một cán bộ khác lên tiếng, cho biết mình đã có tìm hiểu trước một số thông tin và biết được rằng khi biểu tình, cứ mỗi đơn vị thời gian, quần chúng sẽ tạo được sát thương tâm lí ~ED~ lên một khu vực hình vuông có cạnh ~R~ (tức mọi vùng thuộc khu vực này đều chịu sát thương tâm lí ~ED~). Cụ thể, nếu chia bản đồ thành ~N \times M~ vùng được đánh số dòng từ ~1~ đến ~N~ (từ trên xuống dưới) và đánh số cột từ ~1~ đến ~M~ (từ trái sang phải), thì khu vực hình vuông có cạnh ~R~ ở tâm ~(i, j)~ gồm các ô có chỉ số dòng trong khoảng ~[i - M; i + M]~ và chỉ số cột trong khoảng ~[j - M; j + M]~ với ~M = \left \lfloor \frac{R}{2} \right \rfloor~. Quân ta còn điều tra được với bố trí của địch thì vùng nằm ở dòng thứ ~i~ và cột thứ ~j~ sẽ có sức chịu đựng ~H_{i, j}~.

Chúng ta dự kiến có ~T~ đơn vị thời gian (từ thời điểm ~0~ đến ngay trước thời điểm ~T~) để tiến hành khởi nghĩa. Dựa trên dữ liệu hiện tại, anh cán bộ đề xuất một phương án, bao gồm ~Q~ hành động được mô tả bởi bốn số nguyên ~t_j, x_j, y_j, d_j~, cho biết đến thời điểm ~t_j~ thì tâm hình vuông được tạo bởi nhân dân sẽ di chuyển đến tọa độ ~(x_j, y_j)~ và sát thương tâm lí gây ra khi đó sẽ trở thành ~d_j~ (tức là gán ~ED \leftarrow d_j~). Đối với lực lượng bên ngoài bảng ~N\times M~, xem như họ đang hỗ trợ các địa phương khác.

Nhiệm vụ của Phong và các bạn bây giờ là tìm hiểu xem, với phương án của anh cán bộ, chúng ta sẽ giành được bao nhiêu vùng sau thời điểm thứ ~T~. Biết rằng ta giành được một vùng khi sát thương tâm lí chúng ta gây ra cho vùng đó lớn hơn hoặc bằng sức chịu đựng của vùng.

Input

• Dòng đầu tiên chứa năm số nguyên ~N, M, Q, R, T~ (~1 \leq T \leq 10^9~, ~1 \leq R \leq \max(N, M)~ và ~R~ là số lẻ) cho biết kích thước bản đồ đang xét, số hành động trong kế hoạch, kích thước của khu vực hình vuông mà nhân dân biểu tình có thể gây ảnh hưởng và khoảng thời gian biểu tình dự kiến.

• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~M~ số nguyên ~H_{i, 1}, H_{i, 2}, H_{i, 3} \dots, H_{i, M}~ mô tả sức chịu đựng của địch trong các vùng ở dòng thứ ~i~.

• Trong ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên ~t_j, x_j, y_j, d_j~ (~1 \leq d_j \leq 10^9~) mô tả hành động thứ ~j~. Dữ liệu đảm bảo ~t_1 = 0~ và ~t_1 < t_2 < t_3 < \dots < t_Q < T~.

Output

In ra một số nguyên duy nhất là số vùng mà chúng ta giành được sau thời điểm thứ ~T~.

Scoring

Sample Input 1

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

Sample Output 1

1

Sau những ngày tính toán các phương án, không khí trong căn cứ dường như sục sôi hơn bao giờ hết. Những mệnh lệnh quan trọng được soạn thảo, từng chỉ thị được ghi lại bằng chữ viết nắn nót trên giấy dó. Mọi người hiểu rằng, khi thời cơ đến, tin tức phải truyền đi nhanh chóng, đồng loạt. Sự chậm trễ, dù chỉ một ngày, cũng có thể làm lỡ nhịp tổng khởi nghĩa.

Lúc này, chúng ta lại có một nhiệm vụ mới, đó là truyền tải thông tin đến tiền tuyến một cách sớm nhất. Gói tài liệu được bọc trong tấm vải nâu, niêm phong bằng sáp đỏ, giản dị nhưng thiêng liêng. Khi cầm nó trong tay, Phong thấy nhịp tim mình như gắn với từng con chữ bên trong. Đó không chỉ là giấy, mà là mệnh lệnh của lịch sử, là nhịp cầu nối liền khát vọng của hàng triệu con người.

Lục lọi trong kí ức của mình, Phong biết rằng con đường đưa tin đầy gian nan. Các chiến sĩ giao liên len lỏi qua những lối mòn trong rừng. Đêm đến, họ lội qua suối lạnh, men theo sườn núi tối đen như mực. Có lúc, ánh đèn pin từ đồn lính loang loáng chiếu gần sát, buộc họ phải ép mình xuống bãi cỏ ướt sũng. Tiếng giày đinh dồn dập, tiếng quát tháo thô bạo vọng ra khiến tim những người lính đập thình thịch. Nhưng rồi, tất cả qua đi, để lại sau lưng một khoảng tĩnh mịch nặng nề.

Có một lần, Phong cũng lên đường đi làm giao liên. Trên đường đi, Phong nhận ra rằng công việc truyền tin không hề đơn giản. Nó đòi hỏi sự kiên nhẫn, ý chí và cả sự hy sinh thầm lặng. Không ai tung hô những người đưa tin, nhưng nếu thiếu họ, không một chỉ thị nào có thể đến đúng nơi, đúng lúc. Trong khoảnh khắc, Phong thấm thía rằng cách mạng không chỉ được làm nên bởi những tiếng hô vang nơi quảng trường, mà còn bởi từng bước chân lặng lẽ trong đêm tối.

Khi bình minh vừa ló rạng, sau một đêm dài vượt rừng, Phong và đồng đội đến một lán trại nhỏ nằm giữa thung lũng. Nơi đây là điểm tập kết của tiền tuyến. Những gương mặt mệt mỏi nhưng ánh mắt sáng ngời nhìn họ bước vào. Người chỉ huy tiếp nhận gói tài liệu, mở niêm phong, đọc lướt qua những dòng chữ rồi khẽ gật đầu. Không cần nhiều lời, ông nắm chặt tay Phong, ánh mắt rực sáng như ngọn lửa: đó là lời cảm ơn sâu sắc nhất.

Trong lán, bầu không khí bỗng như thay đổi. Những người chiến sĩ trẻ lập tức lấy giấy bút, sao chép chỉ thị, chuẩn bị gửi đi khắp các vùng. Họ biết rằng, mỗi tờ giấy nhỏ này khi đến tay nhân dân sẽ biến thành cờ đỏ, thành khẩu hiệu, thành dòng người xuống đường.

Ngồi trong góc lán, Phong lặng im quan sát. Anh thấy rõ một sự thật: chiến thắng của cách mạng được dệt nên từ những sợi dây liên lạc mong manh nhưng kiên cường. Giữa núi rừng, những gói tài liệu bọc vải nâu trở thành dòng máu chảy xuyên suốt cơ thể dân tộc, nối liền ý chí của lãnh đạo với sức mạnh quần chúng.

Khi trở về căn cứ trong rừng, Phong nhận thấy việc truyền tin thế này là quá chậm và chưa hiệu quả. Phong tính toán được rằng, đến lúc diễn ra chiến đấu thật, mệnh lệnh phải được truyền đi trong không quá ~L~ đơn vị thời gian. Hiện tại, từ căn cứ đến tiền tuyến có thể chia thành ~N~ điểm, trong đó căn cứ là điểm ~S~, còn tiền tuyến là điểm ~T~. Có ~M~ con đường 2 chiều, con đường thứ ~i~ được mô tả bởi 3 số ~u_i, v_i, w_i~, cho biết từ điểm có thể di chuyển qua lại giữa 2 điểm ~u_i~ và ~v_i~ và mất ~w_i~ đơn vị thời gian.

Nhưng may mắn là trước đó, mỗi điểm đã được gán một mã liên lạc ~c_i~. Những điểm có cùng mã liên lạc có thể truyền tin ngay lập tức cho nhau mà không tốn thời gian. Sắp tới, có ~Q~ đợt chi viện, được diễn ra lần lượt từ đợt thứ nhất tới đợt thứ ~Q~, đợt thứ ~j~ sẽ đẩy lùi một số quân địch, cho phép quân ta có thêm phương án liên lạc hai chiều từ điểm có mã liên lạc ~x_j~ đến điểm có mã liên lạc ~y_j~ trong ~z_j~ đơn vị thời gian.

Nhiệm vụ của bạn và Phong bây giờ là tính xem sau bao nhiêu đợt chi viện thì ta có thể truyền tin từ điểm ~S~ tới ~T~ trong không quá ~L~ đơn vị thời gian.

Nếu sau ~Q~ đợt chi viện mà ta không thể truyền tin trong ~L~ đơn vị thời gian, hãy in ra ~-1~ để ban chỉ huy huy động thêm viện trợ.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N~, ~M~ và ~K~ ~(2 \leq K \leq N \leq 10^5~ và ~1 \leq M \leq 10^5)~ lần lượt là số lượng cứ điểm, số con đường ~2~ chiều và số mã liên lạc.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, c_3, \cdots c_n~ (~1 \leq c_i \leq K~), trong đó ~c_i~ cho biết mã liêc lạc của cứ điểm ~i~.

• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~u_i~, ~v_i~ và ~w_i~ ~(1 \leq u_i, v_i \leq N, u_i \neq v_i~ và ~1 \leq w_i \leq 10^9)~, cho biết có thể đi lại giữa ~2~ cứ điểm ~u_i~ và ~v_i~, tốn ~w_i~ đơn vị thời gian.

• Dòng tiếp theo chứa ~4~ số nguyên dương ~Q, L, S, T~ (~1 \leq Q \leq 10^5~, ~1 \leq L \leq 10^{14}~, ~1 \leq S, T \leq N~) lần lượt là số đợt chi viện, số đơn vị thời gian không được vượt quá, vị trí của căn cứ điểm và vị trí của tiền tuyến.

• Trong ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa ~3~ số nguyên dương ~x_j, y_j~ và ~z_j~ (~1 \leq x_j, y_j \leq N~, ~x_j \neq y_j~ và ~1 \leq z_j \leq 10^9~), có ý nghĩa là ~1~ đợt chi viện giúp quân của ta giúp ta liên kết một vùng có mã liên lạc ~x_j~ với một vùng có mã liên lạc ~y_j~ và di chuyển trong ~z_j~ đơn vị thời gian.

Output

• Nếu không thể di chuyển từ ~S~ đến ~T~ với thời gian không quá ~L~ sau ~Q~ đợt chi viện, in ra ~-1~. Ngược lại, in ra số đợt chi viện tối thiểu để ta có thể di chuyển từ ~S~ đến ~T~ với thời gian không quá ~L~.

Scoring

Sample Input 1

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

Sample Output 1

3

Sau khi giúp cơ quan đầu não của ta giải quyết vấn đề về truyền tin, Phong được điều động lên tiền tuyến để hỗ trợ các đơn vị tại đây.

Trong một ngôi nhà nhỏ giữa lòng thủ đô, bầu không khí như bị dồn nén, căng thẳng mà cũng chan chứa niềm hy vọng. Sau bao tháng năm chịu cảnh lầm than, đói khát và áp bức, giờ đây thời cơ đã đến gần. Tại đây, trong gian phòng tối chỉ le lói ánh đèn dầu, các đồng chí lãnh đạo địa phương đang bận rộn. Trên bàn, tấm bản đồ thành phố trải rộng, những dấu bút đỏ đánh dấu trụ sở các cơ quan cai trị của địch, những điểm tập trung đông quần chúng, những tuyến đường di chuyển. Giấy tờ, tài liệu ngổn ngang, nhưng từng nét chữ, từng ký hiệu đều toát lên sự cẩn trọng và quyết đoán.

Phong lặng lẽ đứng bên, quan sát. Anh cảm nhận được sự gấp gáp trong từng hơi thở. Người thì khẩn trương chép lại hiệu lệnh, người khác chỉnh sửa khẩu hiệu, còn ngoài sân, các tổ tự vệ thay nhau luyện tập động tác, chuẩn bị cờ, băng rôn và loa tay. Không khí rộn ràng ấy khiến anh tưởng như nghe được cả nhịp tim chung của dân tộc, đang dồn dập, rạo rực, chờ giây phút bùng nổ.

Một đồng chí phụ trách tuyên truyền mang vào chồng truyền đơn vừa in xong. Tờ giấy còn thơm mùi mực, chữ in rõ ràng: "Việt Nam hoàn toàn độc lập! Toàn dân vùng lên giành chính quyền!". Những khẩu hiệu ấy sẽ được bí mật phát đi khắp nơi, để vài hôm nữa đồng loạt xuất hiện trong tay hàng vạn người dân. Phong cầm một tờ truyền đơn, ngón tay run run. Anh thấy rõ trong từng câu chữ là sức mạnh của niềm tin, của khát vọng cháy bỏng không gì ngăn nổi.

Ở góc phòng, một thanh niên trẻ đang tỉ mỉ khâu lại lá cờ đỏ sao vàng. Mỗi mũi kim, mỗi đường chỉ được thực hiện chậm rãi, trang nghiêm, như gửi gắm cả tấm lòng vào biểu tượng thiêng liêng của Tổ quốc. Ánh đèn dầu hắt lên khuôn mặt anh ta, sáng lên sự quyết liệt và xúc động. Phong nhìn lá cờ ấy, trong lòng chợt dâng trào hình ảnh hàng vạn lá cờ tung bay, như biển đỏ phủ trùm khắp phố phường.

Đêm hôm ấy, vầng trăng sáng rực bên ngoài khung cửa số, tiếng cho sủa vang vọng, khuấy động không gian im ắng của thành phố. Trong nhà, tiếng thì thầm bàn bạc của các lãnh đạo, tiếng sửa soạn của các đồng chí không ngớt, làm Phong cảm thấy vừa hồi hộp, vừa thiêng liêng, như thể mình đang sống lại từng khoảnh khắc trước một cột mốc lịch sử vĩ đại.

Nhiệm vụ của Phong và nhóm của mình là giải mã những mệnh lệnh mới được chuyển đến. Mệnh lệnh được mã hóa bằng một khóa có độ dài ~n = 2^k~ (với ~k~ là số nguyên), được đánh số từ ~0~, gồm các số nguyên không âm. Khóa này cũng đã được mã hóa. để giải mã, nhóm của Phong có thế thực hiện thao tác sau không giới hạn số lần (có thể không thực hiện):

• Chọn hai số nguyên ~p, d~ sao cho ~0\le d\le k~ và ~0\le p\times2^d\le (p + 1)\times 2^d\le 2^k~.

• Đảo ngược thứ tự của các phần tử của khóa trong đoạn ~[p\times 2^d; (p + 1) \times 2^d)~.

Khóa để giải mã mệnh lệnh là khóa có thứ tự từ điển~^\dagger~ bé nhất có thể thu được sau khi thực hiện các thao tác trên một cách tối ưu.

Do Phong đã giải mã được một số khóa nên đã bắt tay vào giải mã mệnh lệnh. Vì thế, bạn hãy giúp Phong giải mã những khóa còn lại để nhanh chóng biết được mệnh lệnh của cơ quan đầu não là gì nhé.

~\dagger~ Dãy ~x_1, x_2, \dots, x_m~ được coi là nhỏ hơn theo thứ tự từ điển so với dãy ~y_1, y_2, \dots, y_m~ nếu:

• Tồn tại một số ~r < m~ sao cho ~x_1 = y_1, x_2 = y_2, \dots , x_r = y_r~ và ~x_{r + 1} < y_{r + 1}~.

Input

Dòng đầu tiên chứa số nguyên ~\mathcal{T}~ cho biết số lượng testcase cần xử lý.

Mỗi testcase gồm ~2~ dòng có định dạng:

• Dòng đầu tiên của mỗi testcase chứa một số nguyên ~k~ cho biết độ dài của một khóa được mã hoá là ~2^k~.
• Dòng thứ hai chứa ~2^k~ số nguyên ~a_0, a_1, a_2, \dots, a_{2^k - 1}~ mô tả khóa được mã hoá.

Output

Với mỗi testcase, in ra một dãy số ~b~ gồm ~2^k~ phần tử trên một dòng riêng biệt, mô tả khóa để giải mã mệnh lệnh.

Scoring

Sample Input 1

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

Sample Output 1

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

Notes

Ở testcase thứ hai của test ví dụ, ta thực hiện hai thao tác sau để biến đổi dãy ~[2, 1, 3, 2]~ thành ~[1, 2, 2, 3]~:

• Chọn ~p = 0~ và ~d = 1~, khi đó đoạn được đảo ngược là ~[0; 2)~, dãy ~a~ được biến đổi thành ~[1, 2, 3, 2]~.

• Chọn ~p = 1~ và ~d = 1~, khi đó đoạn được đảo ngược là ~[2; 4)~, dãy ~a~ được biến đổi thành ~[1, 2, 2, 3]~.

Không khó để chứng minh đây là dãy có thứ tự từ điển bé nhất có thể có được từ quá trình biến đổi trên.

Sau khi cùng đồng đội giải mã các mệnh lệnh, Phong dần chìm vào giấc ngủ. Trong mơ, anh thấy cảnh nhân dân đang hân hoan trong niềm vui giành được chính quyền. Cờ sao phấp phới tung bay, những cánh chim bay lượn tự do trên bầu trời như muốn hòa nhịp cùng hàng vạn người dân ở dưới.

Bỗng một ánh sáng chói lóa từ bầu trời rọi xuống, bao quanh người Phong, khiến anh bừng tỉnh. Anh đã được đưa trở lại thực tại, trong gian phòng đầy những trang sách lịch sử. Kế bên anh là một bức thư không biết xuất hiện từ bao giờ. Đó là thư mời những người thanh niên ưu tú như Phong đến tham dự một trong những buổi huấn luyện đầu tiên cho nhiệm vụ A80 – nhiệm vụ luyện tập và tham gia diễu binh, diễu hành trong Lễ kỷ niệm 80 năm Cách mạng tháng Tám thành công (19/8/1945 – 19/8/2025) và Quốc khánh nước Cộng hòa Xã hội Chủ nghĩa Việt Nam (2/9/1945 – 2/9/2025).

Sáng hôm sau, Phong đến điểm hẹn trong thư. Ánh nắng đầu ngày trải dài trên quảng trường rộng lớn. Những hàng cây ven đường đổ bóng xuống nền gạch đỏ, nơi hàng ngàn bước chân đang dập đều theo nhịp trống. Trên khán đài nhỏ đặt ở góc sân, Phong đứng lặng, đôi mắt dõi theo từng hàng quân diễu bước.

Tiếng hô "Một! Hai!" vang vọng khắp không gian. Dưới nắng sớm, những bộ quân phục xanh, trắng, những lá cờ đỏ sao vàng rực rỡ cùng tung bay. Nhịp bước chắc nịch, ánh mắt kiên định, tất cả tạo thành bức tranh sống động của sức trẻ. Phong cảm nhận rất rõ, trong từng cử động ấy, có cả âm hưởng của những năm tháng lịch sử mà anh vừa được sống lại.

Người chỉ huy tiến tới, mời Phong cùng tham gia quan sát từ vị trí gần hơn. "Chúng tôi muốn thế hệ trẻ tận mắt chứng kiến và tự hào về sự trang nghiêm của đội hình," ông nói. Phong gật đầu, bước xuống sân. Khi khoảng cách gần hơn, anh càng cảm nhận rõ hơn hơi thở của tuổi trẻ: mồ hôi ướt đẫm áo, nhưng gương mặt ai cũng sáng ngời quyết tâm.

Một khoảnh khắc, mắt Phong dừng lại trên lá cờ lớn đang tung bay ở đầu đội hình. Ánh sao vàng chói lòa trong nắng sớm, rực rỡ chẳng khác nào lá cờ năm xưa anh đã từng nhìn thấy bay trong sương trắng của thung lũng. Hình ảnh ấy khiến trái tim anh bồi hồi. Quá khứ và hiện tại, như hai nhịp đập nối liền, cùng hòa chung trong bước đi của dân tộc.

Trong buổi huấn luyện, những thanh niên trẻ tập hô khẩu hiệu. Tiếng hô dội lên, đồng thanh, dõng dạc, như khẳng định tinh thần sắt son với Tổ quốc. Phong chợt nhớ đến những ngày người dân kéo về quảng trường cách đây tám mươi năm, cũng hô vang những khẩu hiệu tương tự, cũng xếp thành đội ngũ gọn gàng, nhưng trong tay không phải vũ khí, mà là niềm tin và khát vọng tự do.

Bầu trời trên quảng trường trong xanh lạ thường. Tiếng chim buổi sớm bay lượn phía xa. Trong nhịp bước của những người trẻ, Phong nghe thấy không chỉ là tiếng diễu binh, mà còn là tiếng vọng từ quá khứ, tiếng gọi của tương lai. Anh hiểu rằng, mình may mắn được chứng kiến hai thời khắc lịch sử: những buổi chuẩn bị cho chiến dịch năm 1945, và một buổi sáng hôm nay – khi cả dân tộc đang chuẩn bị cho ngày hội lớn kỷ niệm 80 năm Cách mạng tháng Tám và Quốc khánh.

Đến lúc nghỉ ngơi, qua lời một chỉ huy đội hình cho biết, việc sắp xếp những người lính sao cho đội hình đồng đều, ngay ngắn là một việc vô cùng quan trọng. Đầu tiên, những người lính sẽ được cho chiều cao. Dựa vào đó, họ sẽ được gán mã số ~1, 2, 3, \dots, N~ theo thứ tự chiều cao tăng dần. Biết rằng, để đội hình đều và đẹp nhất khi nó thỏa đồng thời ~M~ điều kiện có dạng:

• Điều kiện được mô tả bởi ba số nguyên ~L, R, x~, trong đó ~L \leq x \leq R~, cho biết rằng chỉ huy đội hình yêu cầu người lính thấp nhất trong số các người lính ở vị trí ~L, L + 1, L + 2, \dots, R - 1, R~ phải không được đứng ở vị trí ~x~. Nói cách khác, cần sếp đội hình sao cho ~P_x \neq \min_{L \le i \le R} P_i~, với ~P_j~ là mã số của người lính ở vị trí ~j~.

Chỉ huy đã tìm ra được một đội hình ưng ý rồi, nhưng Phong vẫn thắc mắc, với ~M~ điều kiện như vậy thì có bao nhiêu cách sắp xếp đội hình~^\dagger~ thỏa mãn tất cả. Do đội hình khá đông và một mình Phong không tính được, nên Phong nhờ bạn tính giúp và cho Phong kết quả. Kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của đáp án khi chia cho ~19450819~.

~\dagger~ Hai cách xếp đội hình ~A, B~ được xem là khác nhau nếu tồn tại một vị trí có hai người lính khác nhau ở hai cách xếp, tức tồn tại ~j~ sao cho ~A_j \neq B_j~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~ là số người lính và những điều kiện cần thoả mãn.

• Trong ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~L, R, x~ mô tả một điều kiện (~1 \leq L \leq x \leq R \leq n~).

Output

• Gồm một dòng là số đội hình thoả cả ~m~ yêu cầu, chia lấy dư cho ~19450819~.

Scoring

Sample Input 1

3 3
1 3 2
2 3 2
1 2 2

Sample Output 1

2

Sample Input 2

7 7
6 7 7
2 7 2
5 6 6
5 7 7
2 5 5
5 7 6
2 6 3

Sample Output 2

140

Sample Input 3

5 2
2 5 4
4 5 4

Sample Output 3

60

Notes

Ở test ví dụ đầu tiên, hai cách xếp đội hình thỏa mãn yêu cầu đề bài là ~[1, 3, 2]~ và ~[2, 3, 1]~.