PEG Judge - WC01 - The Sixth Sense

Woburn Challenge 2001

Problem 7: The Sixth Sense

Ghosts were kinda scary and somewhat unprofitable, so Cole Sear (the psychic kid) has decided to take his extrasensory perception to new heights and transcend good style and good sense. He’s going to Vegas — Caesar’s Palace, specifically — to start a mind-reading show. On one particular night, unbeknownst to him, several MI6 agents were in his audience – it turns out that hacking into CBS computers didn’t work and thus the only option M was left with was to see if a mind reader could determine the winner. This was the opening act they witnessed:

Cole picks a good looking girl from the audience (note that this is a rule of the Magician’s Guild).
He asks her to pick any number (a whole number) and then follow his simple conditional commands to manipulate that number (explained below).
After a few commands, he asks her to tell him the result she has calculated and from that he will calculate…(drum roll)…all the possible numbers she could have chosen. Note that the old-school mind readers would have settled with only picking the one number that the audience member had chosen, but Cole wanted to go where no fraud had gone before – he would state all the numbers that she could have chosen and <drumroll> … he would do it in ascending order.

Even though he was already revealed as the masked magician, P decides to write a computer program to reveal the secret behind this trick. But then he realizes that he can just write it up as a “contest problem” and someone else will do the work for him. The conditional commands will take the following form:

if A > 7 then A = A / 2 if A = 5 then A = A * 3
...

Note: The girl doesn’t have that good of a memory, so Cole instructs her to stop and start over with a different initial choice of A if she ever gets a result with more than 7 digits in it. (In other words we want only initial values of A for which |A| < 10,000,000 at each step).

Input

The first line contains T, the number of test cases to follow.
The first line of each test case contains an integer L, the number of instructions to follow (1 ≤ L ≤ 100) and the final value of A.
The next L lines are of the form

if <condition> then A = <expression>

where <condition> is one of

A = # A > # A < # A % # = # A / # = #

and <expression> is one of

A + # A - # A * # A / #

# stands for any positive constant integer less than 100
% is to be interpreted as the “mod” operator
/ is to be interpreted as the “div” operator (integer division, ignoring remainder)

Output

For each test case, output all of the possible starting values of A (sorted in increasing order and space-separated), or Liar! if none are possible.

Note

We guarantee that there will be at most 1000 different initial values of A that produce the desired result and furthermore the same is true if we ignore the 1st command, or the 1st and 2nd, or … all but the last command.

Sample Input

3 3 15 if A = 3 then A = A + 2 if A < 10 then A = A * 3 if A % 7 = 5 then A = A + 3 3 12 if A > 5 then A = A + 8 if A > 12 then A = A – 6 if A > 7 then A = A + 1 1 3 if A > 1 then A = A * 2