In this task you have to build a classifier which is based on a list of rules. A classifier is given as input a string which consists of characters 0 and 1. Then, it processes the string using a list of rules, and gives an answer "yes" or "no" depending on whether the string has a required property.

A list of rules consists of rules of the form x → y, where x is the left part and y is the right part. The rules can contain characters 0 and 1 and additional characters A–Z. The right part can also be _, which denotes an empty string.

The memory of a classifier is a string, which is initially the input string. On each step, the classifier finds the first rule in the list whose left part appears in the string, and replaces the first occurrence of the left part with the right part. The classifier repeats this, until the list does not have any rule that could be used. If the final string is empty, the answer is "yes", and "no" otherwise.

For example, the following classifier determines if a string has exactly one zero. The first line contains the number of rules, and the following lines describe the rules.

5
B1 -> B
B -> _
10 -> 01
00 -> A
0 -> B

For example, the string 1101 is processed as follows: 1101 → 1011 → 0111 → B111 → B11 → B1 → B → _. The string is empty, so the answer is "yes".

Then, the string 1010 is processed as follows: 1010 → 0110 → 0101 → 0011 → A11. The string is not empty, so the answer is "no".

Task

Your task is to design a classifier which determines if a string can be generated by repeating a string k times. For example, if k=2, the answer for the string 0101 is "yes" and the answer for the string 0100 is "no".

The input for your program has one line with an integer k, and it has to print a list of rules according to the previous example.

Restrictions

• A list of rules may contain at most 100 rules.
• In each rule, the length of the left part and the length of the right part may be at most 10 characters.
• When your classifier will be tested, the length of the input string in each test is at most 100 characters.
• The classifier may perform at most 10000 steps when processing a string.
• The memory of the classifier may contain at most 1000 characters on each step.

Subtask 1 (19 points)

• k=2

Subtask 2 (24 points)

• k=3

Subtask 3 (27 points)

• k=4

Subtask 4 (30 points)

• k=5