406166: GYM102299 B Russo's Russian

B. Russo's Russiantime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

It is well known that Russian is one of the hardest languages in the world. It is one of the only languages in which declension applies to nouns, adjectives, pronouns and numerals. If you know something about German and have heard of its three complicated declensions, know that there are seven in Russian. Anyway, if you are up to a challenge, try to learn Russian.

What is less known is that there is a Russian variant commonly spoken in Brazil. A Russian family immigrated into Italy in the XVII century. Later, in the wake of the XX century, they came to Brazil, where they live to this day, still preserving their culture and customs. This is the 'Russo' family. Of course, that is not their original surname, but they chose it when mister 'Pshenychnykh', after arriving at Calabria, gave up on trying to teach the Italians how to pronounce 'Pshenychnykh'. Only later he found out that 'Rosso' means red in Italian, but that just made him like the name even more.

Russo's Russian dialect is a mix between Italian, Portuguese, Russian and Calabrian. Its grammar has one of the most complex phrases known to mankind. That became a problem when the descendants of mister Pshenychnykh had to study his finances. Fortunately, the family prospered in Brazil and got really rich. Unfortunately, that created a dispute among the descendants for the wealth and possessions linked to the family's name. Trying to settle things, they went after mister Pshenychnykh's financial notebooks.

Of course, his notes are in the peculiar dialect spoken by the family. Moreover, it is known that mister Pshenychnykh always wrote things respecting the grammar of his dialect — he was really proud of his roots. A note is valid if it a possible expansion of M in the following grammar:

M = H '|' P | '|' M | P
H = M | '$$$'
P = P ':' T | T
T = '{' M '}' | I

As usual, the vertical bar represents possible options for the expansion of a symbol. The characters inside single quotes are the terminal symbols, meaning they are not expanded and appear as they are in the final expression. The symbol \texttt{I} represents any sequence of numerical digits without space. In any other rule, i.e., except in \texttt{I}, it is possible to have any amount of white space separating symbols as described by the rules of the grammar. For example,

{        12}

is a valid expression.

Unfortunately, when the years went by, some of the notes got deteriorated, and not all of the expressions remain correct. Your task is to identify which are still correct, i.e., which are strings that can be obtained expanding \texttt{M} in the grammar above.

\InputFile

The input has a single line with a string $$$s$$$ with at most $$$10^5$$$ characters. Every character can be a whitespace, a digit, or one among the following:

$$$:|{}

Output

Print "YES" if the line supplied is valid, and "NO" otherwise.

ExamplesInput

1

Output

YES

Input

: 1

Output

NO

Input

$ | 2

Output

YES

Input

5 : 14

Output

YES