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 \(T\) độ dài \(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 đang biểu diễn tương tự như xâu \(T\) nhưng có đúng 2 ký tự cách nhau đúng \(k\) vị trí 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ểu diễn về dạng chuỗi 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 virus 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_i\) của \(S\) sao cho \(S_i\) là biến dạng của \(T\).

Dữ liệu vào:

• Dòng đầu tiên chứa xâu \(S\) độ dài \(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 \(T\) độ dài \(m\) biểu diễn ADN ban đầu của virus.
• Dòng cuối cùng chứa số nguyên \(k\).

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

Dữ liệu ra:

• Dòng đầu tiên chứa số nguyên \(p\), là số lần xâu \(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à chỉ số bắt đầu trong \(S\) xuất hiện một biến dạng của \(T\).

Ràng buộc:

• Có 30% số test tương ứng 30% số điểm có \(1 \leq k < m \leq n \leq 200\);
• Có 30% số test khác tương ứng 30% số điểm có \(200 < k < m \leq n \leq 10^4\);
• Có 40% số test khác tương ứng với 40% số điểm có \(10^4 < k < m \leq n \leq 2 \cdot 10^5\).

Input 1

abcaaaa
baab
3

Output 1

2
3 4

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

Input 1

abcaaabcd
aecb
2

Output 1

2
1 6