Problem Description
Let f(s) be a hash function of string s. If s=s0s1…sn−1,f(s)=(∑n−1i=0w(si)basei)modr.
Teacher Mai wants to find two different regular bracket sequences a,b with the same length(≤104) 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≤p,q,r,base≤1018)
Output
For each test case, print two different regular bracket sequences a,b with the same length(≤104) and the same hash value(f(a)=f(b))
Sample Input
4 7 37 10
Sample Output
((()))
()()()
