Linas thích chơi một nhạc cụ mà không ai biết tên. Nhạc cụ có \(S\) lỗ, và Linas có thể chơi \(N\) nốt khác nhau, đánh số từ \(1\) đến \(N\), bằng cách bịt mỗi lỗ theo một trong mười cách, đánh số từ \(0\) đến \(9\).

Mỗi nốt ứng với đúng một cách bịt tất cả các lỗ, được mô tả bằng một xâu chữ số. Nếu bịt theo một cấu hình không tương ứng với nốt nào, nhạc cụ phát ra âm thanh rất khó chịu. Vì thế, Linas thà chơi sai nốt còn hơn dùng một cấu hình không hợp lệ.

Linas tham gia một ban nhạc thường chơi những giai điệu phức tạp với tốc độ rất nhanh. Cậu đã viết một giai điệu, là một dãy số hiệu các nốt, và muốn chơi cùng ban nhạc. Tuy nhiên, Linas chỉ chơi được hai nốt liên tiếp nếu khi chuyển sang nốt thứ hai, cậu phải thay đổi cách bịt không quá \(G\) lỗ so với nốt thứ nhất. Do đó, đôi khi cậu phải chơi một nốt khác với nốt trong giai điệu ban đầu. Mỗi vị trí chơi sai như vậy được tính là một lỗi.

Cho giai điệu ban đầu, hãy tìm một giai điệu đã sửa mà Linas chơi được với số lỗi ít nhất.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N,S,G\): số nốt có thể chơi, số lỗ và giới hạn số lỗ có thể thay đổi giữa hai nốt liên tiếp.

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(S\) chữ số, không có dấu cách. Chữ số thứ \(j\) của xâu thứ \(i\) cho biết cách bịt lỗ thứ \(j\) để chơi nốt \(i\). Không có hai nốt nào có cùng một cách bịt các lỗ.

Dòng tiếp theo chứa số nguyên \(L\), độ dài giai điệu. Dòng cuối chứa \(L\) số nguyên trong đoạn từ \(1\) đến \(N\), là các nốt của giai điệu theo thứ tự.

Dữ liệu ra

Dòng đầu chứa một số nguyên không âm: số lỗi nhỏ nhất. Dòng thứ hai chứa \(L\) số nguyên, là một giai điệu Linas chơi được và đạt số lỗi đó. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le G < S \le 100\).
• \(1 \le L \le 10^5\).

Phân nhóm

• Các bộ test có \(L \le 100\) chiếm tổng cộng \(40\) điểm.
• Các bộ test có \(L \le 5000\) chiếm tổng cộng \(65\) điểm, bao gồm các bộ test ở mục trên.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

5 4 2
1111
2101
2000
0100
0000
7
1 5 4 5 3 2 1

1
1 2 4 5 3 2 1