# Hack it!

Time Limit
2s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/1)
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 Aand 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:
((()))
()()()

Source:

2015 Multi-University Training Contest 9

Submit