// https://oj.uz/problem/view/COI20_zagrade
// try to grab 'entire sequence is valid' subtasks
/* let's start over. what if we just naively match brackets? so we know the sequence is valid for this subtask
* and so s[0] is (. then we must have some ) matching s[0]. like ()<- or (()())<- . also, since the sequence is valid,
* notice that if [0,i] matches then i is definitely ).
* we can tell if [0,i] matches if query(0,i) is 1. but what if it is 0 ? Then 0,i doesn't match. this means that even though
* 0,i might be ( and ) respectively, They don't match because i is matched to some other (. same as simple bracket matching.
* on the other hand, if query(0,i) is 1 then 0, i "match" because i is the correct match for 0.
* what does this mean?
* since sequence is valid then every element must match to _SOMETHING_. it can be a starting point or an ending point.
* lets fix the starting point at 0 first. then to find its match we can query every element 1,2,3,...,n until we get a 1.
* then this is O(N^2) if we repeat for every element. but wait, can we repeat this for every element? say in ((())),
* 0 matches with 6. then we go to 1, it matches with 5, etc. that works. but what if it's an extreme case.
* say ()()(). wait that works also.
* say (())(). then 0 matches with 3.
* wait, why am I using 0-indexing? whatever, we will continue to use 0 indexing from now on.
* say (())(). then 0 matches with 3, then go on to 1. 1 matches with 2. then go on to 4. 4 matches with 5.
* so i think this works but it's O(N^2) queries.
*
* can we improve?
* - 1. obviously every query should have an even length otherwise its always 0.
* - so we can optimise this in query function itself, just return 0 if length is odd
* - why is this current method O(N^2) ? oh, because we may need to traverse the entire sequence to match for each one.
* say ((())), we need to go through the entire string to get the answer for 0, 1, etc.
* how to improve this?
* what if we copy bracket matching method. in bracket matching naively searching for a pair is also O(N^2) right.
* so bracket matching uses a stack. so it's not eager to find the match for a specific starting point now, it pushes it onto
* the stack and tries to find the match later.
* so we shouldnt fix the starting point!
* we should fix the ending point!
* but how to do that?
* say we have a stack, its empty at first.
* OHHH! because if the stack is empty that means we are at index 0 and that means we are definitely an open bracket
* that means we can just push 0 on the stack and look for a mtch later.
* then when 1 comes, how do we check if its a match?
* just run a query. query(0, 1)
* if this is 1 then we just match them and continue on. (decomposed the problem)
* if its 0 then that means 1 must be ( and we push 1 on the stack.
* but wait, is this generalisable to long sequence?
* but wait, at least this optimises it. because we dont need to check with 0 anymore, we can just
* check with the LAST element of the stack! because of how bracket matching works. always matches the inner bracket first,
* if it doesnt match inner bracket it cannot match outer bracket. so we can just skip.
* i think this works. so only O(N) queries!
* so if we see a element that gives a query result of 1 with the top stack element, we just match it with that,
* and then pop both off the stack.
* i think this works.
*
*
*
*/
#include <bits/stdc++.h>
using namespace std;
int n, q;
map<pair<int, int>, int> query_memo; // optimisation
// helpers to query & output
inline int query(int i, int j) {
if (query_memo[{i,j}]) {
return query_memo[{i, j}];
}
if ((j - i + 1) % 2 == 1) {
return 0;
}
cout << "? " << i << " " << j << endl;
int r; cin >> r;
return query_memo[{i,j}] = r;
}
inline int query(int i, int j, const vector<int>& input) {
return query(input[i], input[j]);
}
inline void output(vector<short>&s) {
cout << "! ";
for (int i = 1; i <= n; i++) {
cout << (s[i] == 0 ? '(' : ')');
}
cout << endl;
}
inline void output(vector<char>&s) {
cout << "! ";
for (int i = 1; i <= n; i++) {
cout << s[i];
}
cout << endl;
}
int main() {
cin >> n >> q;
vector<char> out(n+1);
stack<int> st;
for (int i = 1; i <= n; i++) {
if (st.empty()) {
out[i] = '(';
st.push(i); continue;
}
int p = st.top();
int res = query(p, i);
if (res == 1) {
// match
st.pop();
out[p] = '(';
out[i] = ')';
}
else {
// is open because otherwise, it would be a match
out[i] = '(';
st.push(i);
}
}
output(out);
}
