Hack it!

Let $f(s)$ be a hash function of string $s$. If $s=s_0s_1\dots s_{n-1}$,$f(s)=(\sum_{i=0}^{n-1} w(s_i)base^i) \bmod r$.

Teacher Mai wants to find two different regular bracket sequences $a,b$ with the same length$(\leq 10^4)$ and the same hash value$(f(a)=f(b))$, where w("(")=$p$,w(")")=$q$.

Let us define a regular brackets sequence in the following way: Empty sequence is a regular sequence. If $S$ is a regular sequence, then $(S)$ is regular sequences. If $A$ and $B$ are regular sequences, then $AB$ is a regular sequence.

There are multiple test cases. All the test cases are generated randomly.

For each test case, there is one line contains four numbers $p,q,r,base(1\leq p,q,r,base\leq 10^{18})$

For each test case, print two different regular bracket sequences $a,b$ with the same length$(\leq 10^4)$ and the same hash value$(f(a)=f(b))$

4 7 37 10

((()))
()()()

xudyh

2015 Multi-University Training Contest 9