eolymp
bolt
Try our new interface for solving problems
Problems

Марковский цикл

Марковский цикл

Time limit 1 second
Memory limit 64 MiB

Ограниченный алгоритм Маркова состоит из последовательности предложений

s_1s_2...s_Nd_1d_2..d_N,

где s_i и d_i - символы из алфавита A, B, C. Подстрока s_1s_2...s_N называется левой, а d_1d_2..d_N - правой частью предложения.

Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв A, B, C, следующим образом: перебираются все предложения начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.

При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненых до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.

Input data

В первой строке находится исходная строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов.

Длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.

Output data

Вывести два целых числа, разделенных пробелом, - количество ациклических шагов и длину цикла.

Examples

Input example #1
ABABC
C    ->A
AB ->BA
BAA ->ABC
Output example #1
3 3