A *symbolic system of equations* is a set of equations
*x* = *f*(*y*_{1}, …, *y*_{k}), where *x*, *y*_{1}, …, *y*_{k} are
variables and *f* is a *symbol* representing an arbitrary function
with *k* arguments (we say that *f* has *arity* *k*).
A *solution* of a system with *n* variables *x*_{1}, …, *x*_{n}
is any assignment α of expressions to variables in such a way
that for every equation *x* = *f*(*y*_{1}, …, *y*_{k}) it holds
that α(*x*) = *f*(α(*y*_{1}), …, α(*y*_{k})).

Write a program that, given a system of symbolic equations, computes its most general solution, or tells that it does not exist.

**Input**

Input consists of several cases,
each with *n*,
followed by *n* variables in lexicographical order,
followed by the number of equations *m*,
followed by *m* equations in the exact format of the examples.
Variables and functions are words made up of lowercase letters, all different.
Every variable appears at most once in the left side of an equation.
Every function can occur several times,
but always with the same arity, between 1 and *n*.
All arguments of the same function are different variables.
You can assume 1 ≤ *n* ≤ 40.

**Output**

Print, in lexicographical order of the variables, the most general solution of the system, following the format of the examples. Print an empty line at the end of each case.

**Hint**

Take inspiration from a topological sort.

Public test cases

**Input**

3 x y z 2 z = f ( x y ) y = h ( x ) 1 x 1 x = f ( x ) 2 xx yy 2 xx = ff ( yy ) yy = ff ( xx ) 2 abc z 0 6 uu uv w x y z 4 x = f ( uv ) y = gg ( x z ) w = gg ( uv y ) uu = gh ( uv )

**Output**

x -> x y -> h ( x ) z -> f ( x h ( x ) ) No solution! No solution! abc -> abc z -> z uu -> gh ( uv ) uv -> uv w -> gg ( uv gg ( f ( uv ) z ) ) x -> f ( uv ) y -> gg ( f ( uv ) z ) z -> z

Information

- Author
- Enric Rodríguez
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++