Hide

Problem I
if-then-else

Saladin loves to make computers and languages. This time, he has made a CPU that works on $12$-bit words, and created his own language called Salang on top of it. The language itself works well, except for one weird bug. To fix the problem, he has designed a decompiler: A program that takes the machine code and creates an intermediate representation of the program.

The intermediate representation is in a small language that can only do assignments, integer addition and multiplication, if statements and printing. The integer operations silently overflow and wrap around, and the representation has no scoping (a variable @var has the same memory address everywhere). It uses the following EBNF syntax:

<letter> := 'a' | 'b' ... 'y' | 'z'
<var> := '@' letter { letter }
<uint> := ? base 10 of an unsigned int lower than 2^12 ?
<val> := <var> | <uint>
<op> := '+' | '*'
<cmp> := '==' | '<=' | '<'
<assign> := <var> '=' <val> [ <op> <val> ] '\n'
<if> := 'if' <val> <cmp> <val> 'then' '\n' { <statement> }
         [ 'else' '\n' { <statement> } ]
         'endif' '\n'
<print> := 'print' <val>
<statement> := <assign> | <if> | <print>
<program> := { <statement> }

where all values are separated by exactly one space, unless if they begin on a new line.

But the decompiler has forgotten to output the first line! Although all variables are initialised to $0$ before the program starts, the program always begins by assigning the magic variable @a to a fixed number. Before Saladin can start with the debugging, he needs to know the initial value of @a.

Input

The input begins with a single line with two integers: $I$ and $O$. Then comes $I$ lines, the program itself. Finally comes $O$ lines, the numbers this program printed when it ran.

Output

Output the value @a has at the start of the program. If there are multiple valid answers, output the lowest one. If there are no valid answers, output “no solution”.

Limits

  • $0 \leq O < I \leq 100$

  • The program matches the EBNF above

  • The length of a line will always be less than $80$ characters

Sample Input 1 Sample Output 1
12 2
@b = @a + @a
@c = @a * @a
if @c <= @b then
@dx = @b + 3996
if @dx < @a then
print @c
else
endif
endif
@a = @b * @dx
@a = @a + @c
print @a
129
4029
65

Please log in to submit a solution to this problem

Log in