Những kẻ phản diện có ý định thống trị thế giới thường tạo ra các bản sao của chính mình để tránh bị bắt. Bạn đã bắt được một nữ phản diện cùng \(N-1\) bản sao của cô ta và đang cố xác định ai mới là người thật.

Bạn có xâu DNA của từng người, gồm \(M\) ký tự, mỗi ký tự là A, C, G hoặc T. Bạn cũng biết các bản sao không được tạo ra một cách hoàn hảo: xâu DNA của mỗi bản sao khác xâu DNA của người thật ở đúng \(K\) vị trí.

Bạn có thể xác định nữ phản diện thật không?

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\). Mỗi dòng trong \(N\) dòng tiếp theo là một xâu DNA gồm \(M\) ký tự, mỗi ký tự là A, C, G hoặc T.

Dữ liệu bảo đảm có đúng một xâu khác từng xâu còn lại ở đúng \(K\) vị trí.

Lượng dữ liệu vào của bài này khá lớn; chương trình Java cần sử dụng phương thức đọc dữ liệu nhanh.

Dữ liệu ra

In ra một số nguyên là chỉ số của xâu DNA thuộc về nữ phản diện thật. Các xâu được đánh số từ \(1\) theo thứ tự trong dữ liệu vào.

Ràng buộc

• \(3 \le N,M \le 4\,100\).
• \(1 \le K \le M\).
• Mỗi xâu có đúng \(M\) ký tự thuộc tập A, C, G, T.
• Có đúng một xâu khác mỗi xâu còn lại ở đúng \(K\) vị trí.

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (27 điểm): \(3 \le N,M \le 100\).

• Nhóm 2 (19 điểm): \(3 \le N,M \le 1\,800\); mọi ký tự đều là A hoặc C.
• Nhóm 3 (28 điểm): \(3 \le N,M \le 4\,100\); mọi ký tự đều là A hoặc C.
• Nhóm 4 (26 điểm): \(3 \le N,M \le 4\,100\); không có ràng buộc bổ sung.

Ví dụ

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.