Hôm qua John đọc được một bài viết về cúm gia cầm, trong đó nói rằng ADN của virus cúm có thể thay đổi tạo ra biến dạng mới. Theo bài viết đó, nếu ADN của virus hiện tại được biểu diễn như là một xâu \(\mathbf{T}\) độ dài \(\mathbf{m}\) chỉ bao gồm các ký tự in thường (từ a đến z) thì một biến dạng mới rất nguy hiểm là virus có ADN dạng biểu diễn tương tự như xâu \(\mathbf{T}\) nhưng có đúng 2 ký tự cách nhau đúng \(\mathbf{k}\) vị trí (tức là \(\mathbf{T}_{\mathbf{i}}\) và \(\mathbf{T}_{\mathbf{i + k}}\)) bị thay bằng 2 ký tự nào đó khác.

Biết được thông tin này John vội vàng cho lấy mẫu phân tích ADN của một con trong đàn gia cầm của mình, biến đổi về dạng biểu diễn qua các ký tự in thường (từ a đến z) và kiểm tra xem con gia cầm có bị nhiễm vi rút biến dạng hay không?

Giả sử ADN của con gia cầm được biểu diễn bởi xâu S, ADN của virus được biểu diễn bởi xâu T. Con gia cầm được xem là nhiễm virus biến dạng nếu tồn tại xâu con S₁ của S sao cho S₁ là biến dạng của T.

Dữ liệu vào:

+ Dòng đầu tiên chứa xâu \(\mathbf{S}\) độ dài \(\mathbf{n}\) biểu diễn mẫu ADN của con gia cầm John chọn.

+ Dòng thứ hai chứa xâu \(\mathbf{T}\) độ dài \(\mathbf{m}\) biểu diễn ADN ban đầu của virus.

+ Dòng cuối cùng chứa số nguyên \(\mathbf{k}\).

Mỗi xâu đều khác rỗng và có độ dài không quá \({2.10}^{5}\).

Kết quả:

+ Dòng đầu tiên chứa số nguyên p, là số lần xâu \(\mathbf{T}\) biến dạng xuất hiện trong S.

+ Dòng thứ hai chứa p số nguyên theo thứ tự tăng dần, mỗi số nguyên là điểm đầu trong S xuất hiện một biến dạng của T.

Ví dụ:

Giải thích test 1: Có hai biến dạng của xâu \(\mathbf{T} = "baab"\) trong xâu \(\mathbf{S}\) là \("caaa"\) và \("aaaa"\).

Ràng buộc:

+ Có 30% số điểm tương ứng 30% số test có \(1 \leq \mathbf{k} < \mathbf{m} \leq \mathbf{n} \leq 200\);

+ Có 30% số test khác tương ứng 30% số điểm có \(200 < \mathbf{k} < \mathbf{m} \leq \mathbf{n} \leq 10^{4}\);

+ Có 40% số test khác tương ứng với 40% số điểm có \({10^{4} < \mathbf{k} < \mathbf{m} \leq \mathbf{n} \leq 2.10}^{5}\).