Mike needs a bike and he decides to buy a second-hand one to save money. Luckily, he has found a second-hand goods BBS. However, there are so many messages there and it will be extremely boring for him to look through all those messages and figure out which one contains the information he needs. So he decides to write a program to do this.
The problem is: how to determine whether a message is about selling a bike. Mike decides to use a keyword-find-based algorithm. First choose some keywords and then the program checks whether a message contains these keywords or not. For example, he wants to find messages that contain 'bike'，and at the same time have 'sell' or don't have 'buy' ("bike on sell", "bike", "sell bike and buy …"are all what he needs, but "buy bike" is not). Of course he wants his program can be used to handle things more than buying a bike.
As the string matching nature of the keyword-find-based algorithm, regular expression should be quite suitable here. But after a second thought, he throws it away: he even can't figure out what the corresponding regular expression is for a simple query "don't have the word 'buy'".
After further thinking of this problem, Mike comes up with a great idea: combining string matching with Boolean algebra! He names it as "Boolean String Expression".
Formally, a Boolean String Expression is composed of normal strings, ‘&’(and), ‘|’(or) and ‘!’(not). A Boolean String Expression s matches a message M when:
1. s is a normal string, and it's a substring of M
2. s = a & b, a and b are both Boolean String Expressions that match M
3. s = a | b, a and b are both Boolean String Expressions, and at least one of them matches M
4. s = ! a, a is Boolean String Expression which doesn't match M
Precedence of the three operators is: ‘!’ > ‘&’ > ‘|’. And parenthesis can be used to change precedence of operators. Mike's query can be easily expressed as:
bike & (sell | !buy)
Mike is very satisfied with this solution, but he comes to another problem: nearly all expressions can be changed into another form with the same meaning. For example, "bike & (sell | !buy)" has a equivalent form of:
(bike & sell) | (bike & !buy)
It may seem to be obvious to you. However, it confuses Mike a lot and he needs your help to write a problem to check whether two Boolean String Expressions are equivalent. (Equivalent here means: all messages that match one expression will match the other, all messages that don't match one expression will not match the other too)