Description
Big deals only go with smart brains. Now Sempr has a chance to prove that he deserves one.
Sempr is the head of a decoration team. The billionaire flymouse has offered him an opportunity to decorate all his houses and rooms. If the deal goes through, Sempr could spend rest of his life counting notes in his bed. However, large fortune never comes in ease. It turns out that Sempr is doing business with a man who is among the pickiest people in the world. Before his team starts working, flymouse has given him a long list of clauses, violation of any of which will mean “deal’s off”.
In general, each clause in the list is about characteristics of several houses and/or rooms. Here’s a possible clause among others:
The roof of the villa in the mountain is not painted green,
or chandeliers are installed in the downtown office,
or the sea view apartment has a big window.
A clause is always composed of one or more subclauses, connected by the conjunction or if necessary. It is satisfied as long as any of its subclauses is satisfied, whether the rest is satisfied or not. The same subclause can be found in more than one clauses and appear in both positive and negative forms.
Picky as he is, flymouse never creates the nonsense of “mission impossible”. List in hand, how will Sempr fulfil the deal before he can retire for life?
Input
The list of clauses is presented in multiple lines. The clauses are listed one after another, separated by lines containing a single word and if necessary. The subclauses of a clause each occupy a separate line. If a subclause is not the first subclause of a clause, it will be preceded by the word or, which is not part of it. A subclause consists of a sequence of words formed by lowercase letters in the English alphabet. A subclause is considered to be in positive form if it does not contain the word not and in negative form if the word not appears exactly one in it. The word not never appears more than once in a single subclause. If the word not is removed, the negative form of a subclause is exactly the same as its positive form. A clause has only one positive form but can have several negative forms, which are considered equivalent.
The list is non-empty and contains at most 1000 clauses, each consist of at least one and at most six subclauses. No subclauses are repeated in any forms in a single clause. There are at most 120 different subclauses if forms are neglected.
Words on the same line are separated by exactly one space. No lines contain any leading or trailing spaces and there are no blank lines.
Output
Show how Sempr meets flymouse’s demands by telling which subclauses are satisfied and which are not. If there are multiple possibilities, pick one of them. For each subclause (forms neglected) that appears in the input, print its positive form if it is satisfied or otherwise one of its negative forms formed by inserting the word not into the beginning, the end or between any two successive words of its positive form. Subclauses can appear in arbitrary order. Each subclause occupies a separate line. Words on the same line must be separated by exactly one space. The line must not contain any leading or trailing spaces. There must not be any blank lines.
Sample Input
roof of the villa in the mountain is not painted green
or chandeliers are installed in the downtown office
or the sea view apartment has a big window
and
roof of the villa in the mountain is painted green
or chandeliers are not installed in the downtown office
and
the sea view apartment has a big window
Sample Output
roof of the villa in the mountain is not painted green
chandeliers are not installed in the downtown office
the sea view apartment has a big window
http://poj.org/problem?id=2981
