There are given two words x, y and finite series of words (w₁, w₂, ... , w_k).

An operation w * w_i means a connection (concatenation) of word w with another word w_i (1 <= i <= k), i.e. – in other words – is writing a word w_i 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.

Example
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 eventually aa. In both cases we result in the same word: abbaaabadccaa.

Task

• Reads from the text file WYR.IN a length k of a given series of words, then descriptions of two words xand y as well as descriptions of the words from the series: (w₁, w₂, ... , w_k),
• Verifies whether the words x and y can be equalized with the words from the given series. If it is possible it finds the minimal number of operations *, which are necessary,
• write this number in the text file WYR.OUT.

Input

• In the first line of the textfile WYR.IN there is written a positive integer k <= 40. This is the length of the series (w₁, w₂, ... , w_k).
• 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 (w₁, w₂, ... , w_k) – 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 2000.
• The sum of lengths of all given words is not greater than 5000.

Output

In the text file WYR.OUT there should be written:

• One nonnegative integer, the minimal number of operations *, which are necessary to equalize given words x and y,
• or the word NIE (no in Polish), if it is not possible to equalize the words

Examples

For the input file WYR.IN:
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

In the text file WYR.OUT there should be written one integer:
5

For the input file WYR.IN:
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

In the text file WYR.OUT there should be written one word:
NIE

Your program should look for the file WYR.IN in the current directory and produce the output file WYR.OUT in the current directory too. The file containing the source code of your program should have a name WYR.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in the file WYR.EXE