Những Điểm Khớp

Cho một văn bản $T$ và một mẫu $P$. Hãy tìm mọi chỉ số $i$ theo hệ $0$ sao cho đoạn gồm $|P|$ ký tự của $T$ bắt đầu tại $i$ bằng đúng $P$.

Các lần xuất hiện chồng lấn vẫn được tính. Ví dụ, mẫu aa xuất hiện ba lần trong aaaa, tại các vị trí $0,1,2$.

Input

• Dòng đầu chứa văn bản $T$.
• Dòng thứ hai chứa mẫu $P$.

Output

• In mỗi vị trí hợp lệ trên một dòng, theo thứ tự tăng dần. Nếu mẫu không xuất hiện, không in gì.

Constraints

• $1\le |T|\le 10^6$.
• $1\le |P|\le 10^4$.
• Mỗi ký tự của $T$ và $P$ là chữ cái Latin hoặc chữ số. Chữ hoa và chữ thường được xem là hai ký tự khác nhau.

Scoring

• Subtask $1$ ($50\%$ số điểm): $|T|\le 200$ và $|P|\le 50$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

ababaabababa
aba

0
2
5
7
9