Description

There are five logical expressions, called R1, R2, R3, R4, R5. Only the logical variables $a, b, c, d, e, f, g, h$, the logical operations
# (not)
& (and)
+ (or)
and parentheses can be used in the expressions. The precedence of operations is as described above. Parentheses can be used to define a different order of operations.

The operations are defined by the following table.

Suppose that some expressions can be represented (expressed) by a single logical operation with one or two arguments:

• $R_i = R_j$ ($R_i$ is equivalent to $R_j$, i.e. for every assignment of variable values, $R_i$ gives the same value as $R_j$);
• $R_i =$ # $R_j$ ($R_i$ is equivalent to the negation of $R_j$);
• $R_i = R_j$ & $R_k$ (conjunction);
• $R_i = R_j + R_k$ (disjunction);

where ($i \ne k, i \ne j$).

A set of basic expressions is a set such that no other expression not included in the set can be represented (expressed) from it, as defined above.

Write a program to find:

1. Any smallest set of basic expressions.
2. For each expression, any representation (expression) (for expressions that do not belong to the basic set). The representation must be obtained using any single logical operation with one or two arguments, i.e. using expressions from the basic set.

Input Format

Five lines, one expression per line: R1 on the first line, and so on. There are no spaces in the expressions. You may assume the input data is correct. The length of each line is less than $256$.

Output Format

The output should contain $5$ lines, one per expression. On the first line, output the names of the basic expressions. The remaining lines should contain the representation (in the form of an equality / equivalence) of all other expressions (i.e. those not in the basic set), as shown in the example below.

a&(b&b) 
c+c
a&b+c
#a
a&b 

R1
R2
R4
R3=R1+R2
R5=R1 

Hint

Scoring

The scoring of this problem follows the original BOI statement. The full score is $30$.

Notes

This problem comes from Baltic Olympiad in Informatics 1996: Day 1: LOGICAL EXPRESSIONS.
Translated and compiled by @求学的企鹅.

Translated by ChatGPT 5