Ngày qua ngày, mọi thứ vận hành một cách máy móc; ba màu huỳnh quang đơn điệu xếp trước mắt, xung quanh là bóng tối nặng nề. Tương lai dường như chỉ dẫn đến một kết cục tồi tệ.

Sự trống rỗng hoàn toàn. Công việc máy móc tưởng như "đầy đủ" không thể lay chuyển mảnh đất tư tưởng cằn cỗi, dù những điều được nghĩ đến vẫn liên tục tạo ra các "kỳ tích" vô nghĩa.

Kỳ tích mà tôi mong đợi là gì? Có lẽ đó là một sự kiện xác suất nhỏ tác động đến nhiều bộ phận; các bộ phận ấy lại liên hệ với nhau và cuối cùng tạo nên một biến đổi lớn ở tầm vĩ mô.

Tháng nối tiếp tháng, bóng tối dần xâm lấn hy vọng. Trước nỗi tuyệt vọng gần như chắc chắn, tôi chỉ còn có thể cầu mong ánh sáng của kỳ tích lại xuất hiện.

Đông Tước nhận thấy nhiều sự vật tưởng như không liên quan vẫn có thể tạo ra những mối liên hệ kỳ diệu.

Một kỳ tích được biểu diễn bằng ma trận \(3\times3\) \(op\), trong đó \(op(i,j)\in\{0,1,2\}\) với mọi \(i,j\in\{0,1,2\}\).

Với \(0\le i,j<3^n\), viết biểu diễn cơ số \(3\) đủ \(n\) chữ số của chúng là

Định nghĩa

Ba dãy số nguyên không âm \(A,B,C\), mỗi dãy có độ dài \(3^n\), được gọi là chứa kỳ tích \(op\) nếu với mọi \(0\le i<3^n\),

Đông Tước có thể dễ dàng chọn ngẫu nhiên hai dãy \(A,B\) rồi tạo ra \(C\) sao cho ba dãy chứa một kỳ tích. Tuy nhiên, cậu ấy không biết kỳ tích đó là gì và muốn bạn tìm một đáp án khả dĩ.

Nói chính xác hơn, \(A_i\) và \(B_i\) được sinh độc lập, ngẫu nhiên đều trong \([0,p)\), và đề bảo đảm tồn tại ít nhất một ma trận \(op\) thỏa mãn công thức trên. Hãy tìm một ma trận như vậy.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test.

• Dòng đầu chứa số nguyên dương \(t\), số bộ test.
• Với mỗi bộ test:
• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(3^n\) số \(A_0,A_1,\ldots,A_{3^n-1}\).
• Dòng thứ ba chứa \(3^n\) số \(B_0,B_1,\ldots,B_{3^n-1}\).
• Dòng thứ tư chứa \(3^n\) số \(C_0,C_1,\ldots,C_{3^n-1}\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng chín số

Nếu có nhiều đáp án, in bất kỳ đáp án nào.

Ràng buộc

• Các \(A_i\) độc lập và ngẫu nhiên đều trong \([0,p)\).
• Các \(B_i\) độc lập và ngẫu nhiên đều trong \([0,p)\).
• \(0\le C_i<p\).
• Tồn tại ít nhất một \(op\) thỏa mãn.

Chấm điểm

Mỗi test trong bảng dưới đây có giá trị \(10\) điểm.

• Tính chất A: tồn tại \(x,y\in\{0,1,2\}\) sao cho

• Tính chất B: tồn tại \(x,y,z\in\{0,1,2\}\) sao cho

• Tính chất C: tồn tại \(x,y\in\{0,1,2\}\) sao cho

• Tính chất 😩 tồn tại \(a,b\in\{0,1,2\}\) sao cho \(op(i,j)=(ai+bj)\bmod3\) với mọi \(i,j\in\{0,1,2\}\).
• Tính chất E: \(op(i,0)=op(i,1)\) với mọi \(i\in\{0,1,2\}\).
• Tính chất F: \(op(i,j)\in\{0,1\}\) với mọi \(i,j\in\{0,1,2\}\).

Ví dụ

3
1
2 0 2
1 0 0
2 2 0
2
0 0 1 1 1 2 0 0 2
1 0 0 2 1 0 1 2 2
10 10 6 8 5 2 8 9 5
3
0 0 0 1 0 1 1 1 1 2 2 2 2 1 0 2 2 0 0 0 1 1 0 2 1 0 2
2 2 1 2 2 0 1 0 1 1 1 0 1 1 1 0 1 1 0 2 0 0 2 1 1 1 0
70 0 81 0 0 0 124 0 105 0 0 0 0 0 0 0 0 0 11 0 101 0 0 0 25 0 108

1 2 0 0 0 0 0 0 0
1 1 1 0 2 0 0 1 2
0 2 2 0 0 0 2 2 2

Đầu vào của bài có thể lớn; nên sử dụng phương thức đọc dữ liệu nhanh.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.