|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||11||8||7||87.500%|
There are given two words x, y and finite series of words (w1, w2, ..., wk). An operation w ⊕wi means a connection (concatenation) of word w with another word wi (1 ≤ i ≤ k), i.e. is writing a word wi just after the word w.
We want to verify if the words x and y can be equalized with words from the given series. The question is whether it is possible to extend the words x and y with words from the series in order to produce two identical words.
The words abba and ab can be equalized with the words from the series: baaabad aa badccaa cc. In this purpose to the word abba we should add: aa and badccaa, and to the word ab — firstly baaabad, then cc, and finally aa. In both cases we result in the same word: abbaaabadccaa.
Write a program that:
In the first line of the standard input there is written a positive integer k, k ≤ 40. This is the length of the series (w1, w2, ..., wk). In the second and the third line there are descriptions of the words x and y. In the following k lines there are descriptions of the succeeding words in the series (w1, w2, ..., wk)) — each description in a separate line. A description of the word consists of a natural number, which is the length of the word, and a word itself written as a series of characters. The number and the word are separated by a single space. Each word consists only of small English letters from a to z and its length is not greater than 2,000. The sum of lengths of all given words is not greater than 5,000.
To the standard output there should be written:
4 4 abba 2 ab 7 baaabad 2 aa 7 badccaa 2 cc
4 1 a 2 ab 2 bb 2 ab 2 ba 2 aa