Bình đang cần kiểm tra xem một xâu \(P\) có xuất hiện trong xâu S hay không. Bình muốn dùng hash xâu để so sánh nhanh. Hãy giúp Bình xác định tất cả vị trí xuất hiện của P trong \(S\).

Định dạng đầu vào

• Dòng đầu chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng thứ hai chứa xâu \(P\) (\(1 \le |P| \le |S|\)).
• Các xâu chỉ gồm chữ cái in thường.

Định dạng đầu ra

• Dòng đầu là số lượng vị trí xuất hiện của \(P\) trong \(S\).
• Dòng thứ hai là các vị trí bắt đầu (đánh số từ 0).

Ví dụ

Input:

aabcabaab
ab

Output:

3
1 4 7

Ràng buộc

• 40% số điểm: \(|S| \le 1000\).
• 60% số điểm còn lại: \(|S| \le 10^5\).