Have you ever hoped to change history, like me? I guess so. Many people think it’s logically impossible to change history, because the new history would evolve into a new present (here “present” means “now”, not “gift”), leading to some contradicting facts. While I haven’t find a way to do time-travel and change history (if you know the way, please tell me!!!), at least I don’t think it’s logically impossible, because we can never sense the whole world (or worlds, if you believe in parallel universe/multiverse theory. See: http://en.wikipedia.org/wiki/Multiverse). If we’re clever enough, we can make a very small change to the history, which would evolve into a different, but consistent present (that means we can’t sense the difference), which would in turn evolve into a better future! Let’s make a thought experiment (See: http://en.wikipedia.org/wiki/Thought_experiment): • There are x possible events in the past, labeled a1 ∼ ax. • There are y possible events now (but some of them may be unable to sense), labeled b1 ∼ by. • There are z possible events that may happen in near future, labeled c1 ∼ cz. • Present events only depend on past events, with known deterministic rules. • Future events only depend on present events, with known deterministic rules. • Make some changes to the past events (happened->not happened, and vice versa) so that the sensed present events remain the same, then some of the future events will change. All these future events are good, so I want to maximize the number of these future events that will actually happen, by changing some of the past events. If there are more than one way to change history, make the smallest change (i.e. change the minimal number of past events). To simplify the problem, each of the rules mentioned above is described by “event = formula”, where “formula” is a string representation of a boolean formula which satisfies: • Only three operators: AND (&&), OR (||), NOT (!) are supported. • NOT has the highest priority and will not be repeated. i.e. !!x is invalid (but !(!x) is valid). • AND and OR has the medium and lowest priority. The associativity of both AND and OR is leftto-right. i.e. x&&y&&z is actually (x&&y)&&z. • Parentheses have usual meanings. • There will be no whitespace characters within the formula. Input The first line contains a single integer T (T ≤ 1000), the number of test cases. Each test case begins with three positive integers x, y, z (1 ≤ x, y, z ≤ 15). The second line contains x 0-1 integers, describing the past (before we change it). The i-th integer is 1 if and only if event ai happened in the past. Each of the following y lines contains the formula of b1 ∼ by (in this order). If the formula is preceded by an asterisk (‘*’), that means we can sense whether that event is happening now (i.e. that boolean variable should not be changed). Otherwise that event can’t be sensed. The following z lines contain the formulae of c1 ∼ cz (in this order), in the same format, except that there will be no asterisks. The lines containing rules will not have any whitespace characters inside.
2/2 Output For each test case, print ‘Increased from a to b.’. If we’re unable to get more good future events, print ‘Unable to improve future.’. If there is any solution, print the list of changed past event in the second line. If there is more than one solution, print the lexicographically smallest (when doing comparison, regard the solution as a list of integers). Print a blank line after each test case. Sample Input 3 212 01 b1=a1&&a2 c1=b1 c2=b1 212 01 *b1=a1&&a2 c1=b1 c2=b1 345 000 *b1=a1&&(a3||a2) b2=!a2 b3=a2&&a3 b4=a1 c1=!b2 c2=b3 c3=b4 c4=b2||!b4 c5=!b2||!b4 Sample Output Case 1: Increased from 0 to 2. a1 Case 2: Unable to improve future. Case 3: Increased from 2 to 4. a2 a3