Hack it!

Problem Description

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.

Input

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})$

Output

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))$

Sample Input

4 7 37 10

Sample Output

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

Author

xudyh

Source

2015 Multi-University Training Contest 9