Adam has just implemented a string substring search algorithm, and he claims it works faster than the traditional KMP (Knuth–Morris–Pratt) algorithm. To celebrate this, Adam decided to create a new language called PION (which he claims is an abbreviation for "Purely Instruction-based ON-the-fly language"), which is based solely on string substring searching.

The PION language consists of only two types of instructions: pattern:replacement and pattern::replacement. Here, pattern and replacement can be empty strings, and their characters have ASCII codes between 32 and 126. They cannot start or end with a space (ASCII code 32), and any such spaces will be ignored. For example, " a b : " is a valid instruction where the pattern is "a b" and the replacement is "" (an empty string).

A program in PION consists of a number of instructions. When the program is executed, the input string is stored in a buffer. For each round, the interpreter scans all instructions. For each instruction, the pattern string is searched for in the buffer to see if it appears as a substring. The first such instruction (where the pattern appears as a substring) will be executed. To execute an instruction, the first occurrence of the pattern string is replaced by the replacement string. If the pattern string is empty, the replacement string is inserted at the beginning of the buffer. After executing a :: type operation, the program stops. After executing a : type operation, another round begins. If no operation is executed in a round, the program also stops. The output of the program is the final string in the buffer.

To maintain execution speed, Adam set the following limits:

• The length of the program (total number of characters) cannot exceed 1000.
• At most 50,000 rounds can be executed.
• After each round, the length of the string in the buffer cannot exceed 500.

To demonstrate the power of this language, Adam designed 10 computational tasks. Your task is to solve these tasks using the impressive PION language!

Examples

Input 1

a

Output 1

a

Note

Consider the following task: If the input string contains any "a", output it as is; otherwise, delete all "x"s from the input string and output it.

Below is a PION program that solves this task. Of course, the last line is unnecessary.

a::a
x:
excited::excited

Grading

For each task, if your program cannot correctly complete the computational task within the limits mentioned above, you will not receive any points. Otherwise, your score depends on the provided .in file. The second line of the .in file contains ten integers. If the number of lines in your program does not exceed $x$ of them, you will receive $x$ points.

In the contestant folder, a checker.cpp is provided. After compiling, run checker to get your score, or checker x to get execution details on input $x$. Except for the random number generator and the input/output format, the checker in the judging system is identical to the provided checker.

Each of the following tasks is worth 10 points (see the Grading section for details). Their scoring parameters are provided as lang1.in-lang10.in. For convenience, after the scoring parameters, we also provide the descriptions of these tasks in the corresponding .in files.

• Task 1: Input a string of length 1-20 containing only 'o'. If its length is odd, output "odd", otherwise output "even". For example, ooo->odd, oooo->even.
• Task 2: Input a string of length 3 to 10 containing only 'o', replace the third 'o' from the right with 'x'. For example, oooo->oxoo.
• Task 3: Input a string of length 1 to 9 containing only 'o', and output a string of length 10 minus the original length. For example, oooo->oooooo.
• Task 4: Input a string of length 1 to 20 containing only '0', '1', '2', and output the sum of its digits modulo 3. For example, 012->0, 221->2, 112->1.
• Task 5: Input a string of digits of length 1 to 20 containing only '0' and '1', and invert each digit. For example, 01->10, 100->011.
• Task 6: Input a string of digits of length 1 to 20 containing only '0' and '1', and output it in reverse. For example, 00101->10100.
• Task 7: Input a string of digits of length 1 to 200 containing only '0' and '1', sort it and output it. For example, 00101->00011.
  • Special constraint: The number of rounds cannot exceed 500 (instead of 50,000).
• Task 8: Input a string containing only 'o' with an even length from 2 to 30, and insert the character '|' in the exact middle. For example, oooo->oo|oo.
• Task 9: Input a string of length 6 containing only 'l' (lowercase L) and '1' (one), and insert 1, 2, 3, 4, 5 'o's between adjacent characters. For example, 1ll1l1->1oloolooo1oooolooooo1.
• Task 10: Input a string of length $n^2$ ($1\le n\le 14$), and output a string of length $n$ containing only 'o'. For example, ooooooooo->ooo.