Các Vị Trí Khớp

Cho văn bản $A$ và mẫu $B$. Một vị trí $i$ hợp lệ nếu đoạn của $A$ bắt đầu tại $i$ và có độ dài $|B|$ bằng đúng $B$. Các vị trí được đánh số từ $1$; những lần xuất hiện chồng lấn vẫn được tính.

Input

• Dòng đầu chứa $A$.
• Dòng thứ hai chứa $B$.

Output

• In mọi vị trí hợp lệ theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có vị trí nào, in $0$.

Constraints

• $1\le |A|,|B|\le 10^6$.
• Hai xâu chỉ gồm chữ cái thường $a,\dots ,z$.

Scoring

• Subtask $1$ ($50\%$): $|A|,|B|\le 2000$.
• Subtask $2$ ($50\%$): Không có giới hạn bổ sung.

Example

bananana
ana

2 4 6