Tèo có văn bản \(T\) và nhiều pattern. Với mỗi pattern, Tèo muốn biết tất cả vị trí xuất hiện của nó trong \(T\) (các vị trí có thể chồng lấn). Hãy giúp Tèo!

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

• Dòng đầu: xâu \(T\) (\(1 \le |T| \le 10^5\)), gồm chữ cái in thường a..z.
• Dòng hai: số nguyên \(K\) (\(1 \le K \le 10^5\)).
• \(K\) dòng tiếp theo: mỗi dòng là một pattern, tổng độ dài không quá \(10^5\).

Định dạng đầu ra

• Với mỗi pattern xuất hiện ít nhất một lần, in ra dòng: <id> <số_lần> <vị trí 1> <vị trí 2> ... (các vị trí 0-indexed, cách nhau bởi khoảng trắng).
• Các pattern không xuất hiện thì không in.
• In theo thứ tự pattern id từ 0 đến K-1.

Ví dụ

Input:

aaaa
3
a
aa
ab

Output:

0 4 0 1 2 3
1 3 0 1 2

Ràng buộc