Trong một lần tham dự kỳ thi CTF (Capture The Flag), Đức gặp một thử thách khôi phục dữ liệu đặc biệt khó. Để tìm được flag, Đức vận dụng những kiến thức giải thuật đã được tôi luyện trong ba năm trung học phổ thông và nhận ra rằng thử thách về bản chất có thể được phát biểu dưới dạng bài toán sau:

Một chương trình lưu trữ cũ của VibeKode biểu diễn mỗi tệp bằng một ma trận gồm ~R~ hàng và ~C~ cột. Mỗi phần tử của ma trận là một chữ cái in hoa trong bảng chữ cái tiếng Anh.

Sau khi các cột bị xáo trộn, tệp được lưu dưới dạng ma trận ~B~. Để đọc lại tệp, chương trình cần một khóa phục hồi gồm ~C~ số nguyên ~s_0, s_1, \ldots, s_{C - 1}~. Các giá trị trong khóa thuộc đoạn từ ~0~ đến ~R - 1~ và đôi một khác nhau.

Nếu thử một khóa ~s~, ma trận được khôi phục ~A~ được xác định bởi:

$$ A[r][c] = B[(r + s_c) \bmod R][c] $$

với mọi ~0 \leq r < R~ và ~0 \leq c < C~. Nói cách khác, khóa ~s_c~ dịch vòng cột thứ ~c~ của ma trận ~B~ một lượng ~s_c~.

Khóa phục hồi đã bị thất lạc. Từ một bản sao lưu, VibeKode biết chính xác ~K~ hàng đầu tiên của tệp gốc. Các hàng này tạo thành ma trận ~P~ gồm ~K~ hàng và ~C~ cột. Tuy nhiên, một số ký tự trong ma trận lưu trữ có thể đã bị hỏng, nên không phải lúc nào toàn bộ tệp cũng có thể được khôi phục đúng.

Một cột ~c~ được xem là khôi phục đúng nếu:

$$ A[r][c] = P[r][c] $$

với mọi ~0 \leq r < K~.

VibeKode cần kiểm tra ~T~ tệp độc lập. Với mỗi tệp, hãy xác định có tồn tại một khóa gồm các giá trị đôi một khác nhau sao cho mọi cột đều được khôi phục đúng hay không.

Dữ liệu vào

Vào từ file văn bản FILESHIFT.INP gồm:

• Dòng đầu tiên chứa số nguyên ~T~ (~1 \leq T \leq 20~), là số tệp cần kiểm tra.
• Mỗi tệp được mô tả bởi:
  • Dòng đầu tiên chứa ba số nguyên ~R, C, K~ (~1 \leq K, C \leq R \leq 2 \cdot 10^5~).
  • ~R~ dòng tiếp theo mô tả ma trận ~B~. Mỗi dòng là một xâu gồm đúng ~C~ chữ cái in hoa.
  • ~K~ dòng tiếp theo mô tả ma trận ~P~. Mỗi dòng là một xâu gồm đúng ~C~ chữ cái in hoa.
• Tổng ~(R + K) \cdot C~ trên tất cả các tệp không vượt quá ~5 \cdot 10^6~.

Dữ liệu ra

Ghi ra file văn bản FILESHIFT.OUT kết quả theo yêu cầu sau:

• Với mỗi tệp, in ra YES nếu tồn tại một khóa khôi phục đúng mọi cột; ngược lại, in ra NO.

Ví dụ 1

Input

2
5 3 2
XHD
AZE
BGD
AHE
BGZ
AGD
BHE
3 2 1
XY
AB
ZX
AB

Output

YES
NO

Giải thích

Với tệp thứ nhất, có thể chọn khóa ~(s_0, s_1, s_2) = (1, 2, 0)~. Ba giá trị trong khóa đôi một khác nhau. Hai hàng đầu của ma trận khôi phục khi đó lần lượt là:

AGD
BHE

Do đó, cả ba cột đều được khôi phục đúng và kết quả của tệp này là YES.

Với tệp thứ hai, để khôi phục hàng đầu thành AB, cả hai cột đều buộc phải sử dụng độ dịch ~1~. Do các giá trị trong khóa phải đôi một khác nhau, không thể khôi phục đúng đồng thời cả hai cột. Kết quả của tệp này là NO.

Ràng buộc

• Subtask 1 (30%): Trong mỗi tệp, ~K = 1~ và với mỗi cột ~c~, có đúng một giá trị ~s~ thỏa mãn ~B[s][c] = P[0][c]~.
• Subtask 2 (20%): Trong mỗi tệp, ~R \leq 100~. Ngoài ra, với mỗi độ dịch ~s~, có nhiều nhất một cột ~c~ sao cho việc chọn ~s_c = s~ sẽ khôi phục đúng cột ~c~.
• Subtask 3 (20%): Trong mỗi tệp, với mỗi độ dịch ~s~, có nhiều nhất một cột ~c~ sao cho việc chọn ~s_c = s~ sẽ khôi phục đúng cột ~c~.
• Subtask 4 (30%): Không có ràng buộc nào thêm.