PEG Judge - WC16 #2 - Most Illogical

Woburn Challenge 2016-17 Round 2 - Senior Division

Problem 1: Most Illogical

Mr. Speck, the Vulcan chief engineer aboard the Starship Enterprise, has grown tired of his crewmates' illogical tendencies. He's found that, not only is the veracity of their statements often questionable, they sometimes even make claims which are objectively false! He'd like to ascertain the truth of some statements made by his colleagues in order to set them straight.

Mr. Speck has modeled a certain statement made by one of his crewmates as a Boolean expression, consisting of a sequence of N (3 ≤ N ≤ 99, N is odd) strings. Starting from the first string, every other string is a Boolean literal representing the veracity of a particular claim, which is either "true", "false", or "unknown". Starting from the second string, every other string is a Boolean operator, either "or" or "and".

Order of operations applies to this expression, with "and" having higher precedence than "or". For example, the expression "false or true and false" evaluates to "false or (true and false)" = "false or false" = "false".

Mr. Speck is interested in the accuracy of the entire statement - that is, the value of the whole Boolean expression. If every Boolean literal within it was known to be either "true" or "false", then the expression could be evaluated to similarly be either "true" or "false". However, each "unknown" literal may independently be either "true" or "false", which may cause the expression's value to be uncertain. If the expression can either evaluate to "true" or "false" depending on the actual values of its "unknown" literals, then the expression's value is considered to also be "unknown".

Please help Mr. Speck determine the value of the Boolean expression, so that he may reprimand his crewmate accordingly!

In test cases worth 3/15 of the points, all of the operators will be "or".
In test cases worth another 3/15 of the points, all of the operators will be "and".
In test cases worth another 3/15 of the points, none of the Boolean literals will be "unknown".

Input Format

The first line of input consists of a single integer N.
The second line consists of N space-separated strings representing the Boolean expression.