Repetition-Free Formula

Nick studies Boolean logic, and his specialty is repetition-free functions. A Boolean function is repetition-free (also called read-once) when it can be written as a formula in which every variable occurs exactly once.

Logical formulas use the following syntax:

• Variables — the letters a to k.
• Parentheses — if E is a formula, then (E) is a formula.
• Negation — ~E is a formula for any formula E.
• Conjunction — E1 & E2 & ... & En.
• Disjunction — E1 | E2 | ... | En.

The operators are listed from highest priority to lowest: ~ (NOT), then & (AND), then | (OR).

You are given a Boolean function described by such a formula, which may repeat variables. Decide whether the function it computes is repetition-free, and if it is, produce a repetition-free formula for that function.

The single line of input contains the Boolean function as a string built from the characters a..k, (, ), spaces, ~, &, and |, where ~, &, and | denote NOT, AND, and OR respectively. Tokens may be separated by any number of spaces. The line contains at most 1000 characters, and the formula is syntactically correct.

Print No if the function is not repetition-free. This includes every constant function (constant true or constant false), because a constant cannot be written without repeating a variable.

Otherwise print Yes on the first line and, on the second line, the canonical repetition-free formula defined by the rules below. Because a function can have many equivalent repetition-free formulas, exactly one canonical form is required.

• Only variables that the function actually depends on appear; a variable that does not affect the result is dropped (for example, a | b & ~b equals a).
• Every negation is pushed onto a variable, so ~ appears only immediately before a variable, as in ~a; never write ~(...).
• The formula is a tree of & and | nodes over single-literal leaves. Adjacent equal operators are merged, so no & node has a & child and no | node has a | child.
• Inside each node, order the operands by the alphabetically smallest variable each operand contains. Operands of one node use disjoint variables, so this order is unique.
• Put exactly one space on both sides of every binary & and |. Add parentheses only where precedence requires: an operand joined by | that sits directly inside a & node is wrapped in parentheses; nothing else is parenthesized.

The output line contains at most 1000 characters.