Cho trước một xâu ~S~, bạn hay tìm các xâu con của ~S~ sao cho khi sắp xếp lại các kí tự trong xâu con ấy, ta được xâu ~hatrong~

Input

• Gồm một dòng chứa xâu ~S~ ~(7 \le |S| \le 10^6~ với ~|S|~ là độ dài của xâu ~S~)

Output

• Dòng đầu in ra số nguyên n: Số lượng xâu con của ~S~ thỏa mãn đề bài
• n dòng tiếp theo, mỗi dòng in ra xâu con tìm được. Nếu có nhiều xâu con giống nhau thì vẫn in ra chúng miễn sao đảm bảo in đúng thứ tự xuất hiện của chúng trong xâu ~S~.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~|S|\le 10^3~.
• Subtask ~2~ (~60\%~ số điểm): ~|S|\le 10^6~.

Ví dụ

Input

trgnhoabc

Output

1
trgnhoa

Giải thích ví dụ

• Có một xâu con thuộc ~S~ thỏa mãn đề bài là ~trgnhoa~, sau khi sắp xếp các kí tự trong xâu này lại ta sẽ được xâu ~hatrong~