Ограниченный алгоритм Маркова состоит из последовательности предложений \textbf{s_1s_2...s_N} → \textbf{d_1d_2..d_N}, где \textbf{s_i} и \textbf{d_i} - символы из алфавита \textbf{A}, \textbf{B}, \textbf{C}. Подстрока \textbf{s_1s_2...s_N} называется левой, а \textbf{d_1d_2..d_N} - правой частью предложения. Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв \textbf{A}, \textbf{B}, \textbf{C}, следующим образом: перебираются все предложения начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается. При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненых до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими. \InputFile В первой строке находится исходная строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов. Длина исходной текстовой строки и левых частей предложений - от \textbf{1} до \textbf{12} букв, количество предложений - от \textbf{1} до \textbf{50}. \OutputFile Вывести два целых числа, разделенных пробелом, - количество ациклических шагов и длину цикла.