Thang Kardashev là một phương pháp đo mức độ phát triển của một nền văn minh, được đề xuất lần đầu tiên bởi nhà thiên văn học Xô Viết Nikolai Semenovich Kardashev vào năm ~1968~. Theo lý thuyết, thang đo Kardashev sự phát triển của một văn minh gắn liền với việc sử dụng năng lượng; căn cứ vào khả năng lợi dụng năng lượng cũng như mức độ thực dân hóa không gian của một nền văn minh. Thang đo gồm ba bậc văn minh bao gồm:

• Loại I, có thể sử dụng được toàn bộ năng lượng của hành tinh mẹ.
• Loại II, có thể sử dụng được toàn bộ năng lượng từ mặt trời của nó.
• Loại III, có thể sử dụng được toàn bộ năng lượng trong một thiên hà.

Ngoài ra, khoa học viễn tưởng cũng đã đề cập đến nền văn minh loại VII, có khả năng bẻ cong không – thời gian.

Tiến sĩ Doom là nhà khoa học lõi lạc đến từ tương lai, khi loài người đã trở nên thịnh vượng, phát triển thành nền văn minh loại II. Ông đã thành công chế tạo cỗ máy quay ngược thời gian và trong một lần quay vì thế kỉ thứ ~XXI~ để tìm hiểu về đại dịch COVID, ông đã giao tiếp với một nhà khoa học trẻ tên Barrak về những điều xảy ra trong tương lai. Tuy nhiên do sống ở hai thời đại khác nhau nên hai người đã gặp tình trạng bất đồng về ngôn ngữ. Cụ thể, tuy đều cùng sử dụng chữ cái latinh nhưng mỗi chữ cái lại được thay thế bằng chữ cái khác bất kỳ, các chữ cái giống nhau thì được thay thế giống nhau.

Ví dụ: đều nói về tương lai, nhưng Barrak sử dụng từ ~future~ còn Doom sử dụng từ ~qwewty~ do ~f \rightarrow q~, ~u \rightarrow w~, ~t \rightarrow e~, ~r \rightarrow t~, ~e \rightarrow y~.

Vì cỗ máy thời gian chỉ cho phép tiến sĩ Doom quay về trong một khoảng thời gian cố định và không thể nào trở lại thời điểm ấy một lần nào nữa. Nên khi sắp kết thúc thời gian, ông đã nói một câu được mô tả bằng văn bản ~t~ và một cụm từ được mô tả bằng văn bản ~p~. Vì chưa có nhiều thời gian nói chuyện nên ông chưa kịp mã hóa ngôn ngữ tương lai. Cho nên ông chỉ có thể tim ra các vị trí tiềm năng, là những vị trí ~i~ mà ~t_i, t_{i+1}, t_{i+2}, ... t_{i+length(p)-1}~ có thể mã hoá văn bản ~p~.

Yêu cầu: cho ~2~ xâu khác rỗng ~t~ và ~p~. Các kí tự của xâu có mã ~ASCII~ nằm trong phạm vi ~[33,126]~. Hãy xác định các vị trí tiềm năng.

Dữ liệu vào

• Dòng đầu tiên chứa văn bản ~t~ sao cho độ dài của ~t~ không vượt quá ~2 \times 10^5~ kí tự.
• Dòng thứ hai chứa văn bản ~p~ có độ dài không vượt quá độ dài của ~t~.

Dữ liệu ra

• Dòng đầu tiền gồm một số nguyên ~k~ – số lượng các vị trí tiềm năng.
• Dòng thứ hai gồm ~k~ số nguyên – các vị trí tiềm năng theo thứ tự tăng dần

Ràng buộc

• ~30\%~ test của đề bài thỏa mãn: độ dài của ~t~ không vượt quá ~200~ kí tự
• ~70\%~ test của đề bài thỏa mãn: không có điều kiện gì thêm.

Ví dụ

Input

abacabadabacabdb
aba

Output

7
1 3 5 7 9 11 14