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\).