Hack it!

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 Aand 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≤p,q,r,base≤1018)

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

4 7 37 10

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

2015 Multi-University Training Contest 9