You're a data analyst at a tech company, working on enhancing user experience by understanding user communication patterns across various platforms. Your team has gathered a dataset consisting of N distinct keywords that appear in chat conversations, social media posts, hashtags, and text messages. By identifying common patterns in these words, you can gain insights into popular phrases or topics being discussed among users.

Your task is to develop a program to identify recurring sequences of characters that appear in these keywords. Only sequences with a minimum length of three repeat within the same keyword itself. For every such recurring sequence, generate its next dictionary permutation (i.e., the next dictionary word formed by rearranging its letters) as the output; if the sequence is already the last possible arrangement of its letters in dictionary order, output the sequence itself. Finally, print all resulting sequences in ascending dictionary order.

Read the input from STDIN and print the output to STDOUT. Do not print arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail.

Problem

Input

Output