// https://oj.uz/problem/view/COI20_zagrade
// try to grab 'entire sequence is valid' subtasks
/* observations for q2.
* u can very easily get the first 2 subtasks, because notice that
* only querying on an even length range can give information. so we just query on
* all (N^2/4) even length ranges and then piece together the answer.
*
* but how to piece together the answer once we have the query results?
* if answer is yes, then it's simple, assign () to the endpoints.
* but if no, then we need to look at where the issue is.
* but how to check?
* I think if u start from the middle of the string and see the result for that, it's either
* yes (which is easy) or no. if no ,then it can be )( or (( or )). how to determine which one?
* let's say (()()), it is valid. that should be easy to check.
* but what if it is (())() ? also valid.
* but what if it is ())(() ? not valid. but then we know () is valid and () is valid. so we can tell that
* the middle is )(. but wait, what observation can we derive here? what if it was )()(() ? or ))(()( ?
* well, wait wait wait. we have queried every segment of length 2, this means we have queried [1,2],[2,3],...
* so for example let's take the example just now, ))(()(. we know [1,2],[2,3],[3,4] all invalid. only [4,5] is valid.
* [5,6] is invalid as well. so let's consider 1. it can be ( or ), no info gained yet. but let's consider 2. if it was (
* then 3 must be (. then 4 must be ( . this would continue forever if we didn't have any () pair confirmed. but we do. so when
* we see 4, we see it contradicts. so , our original assumption was wrong and 2 must be ). similarly we can work back...
* wait! working backwards!
* so whenever we see a pair () we can work backwards, based on the results of our queries, to find the correct answers for the characters
* before it.
* so say there we knew [4,5] was (),
* . wait . i made a mistake. 4 must be (, not ). i have corrected it above.
* this means there wasn't actually a contradiction if we assumed 2 was (. for example:
* )((()) was a possible way that fit all my assumptions, yet is not the answer.
* so how to check if it's correct overall or not?
* to remind myself, the correct answer is ))(()(.
* well, we knew that [3,6] was not a correct pair. can we try to use that? [3,6] is either (( [correct answer] or
* )) or )(. but if it was )) then we have no more )) and so sequence has to be (()()). which is valid. but this doesn't
* generalise to large sequences, because we likely always have ( and ) left.
* if it was )(, then ...
* wait, this is getting too complicated. i don't think breaking it into such branches of logic helps here. to summarize, i think
* working backwards is a part of the intended solution. but how? we need to be prepared for a difficult case where we have few ()s to '
* work on. our solution probably works only for the case where the sequence is valid. because then we are definitely gonna have
* a lot of ()s to work on.
*
* that seems to be the easier way to proceed - instead of solving it for small N first, let's try to solve it for the valid case
* first. but do we really have a lot of ()s to work on? what if they were flipped like, ()()() ? oh right, in that case we still have 3
* valid ones. i think this is quite easy to prove, because of the addition properties of valid sequences as stated in the qn.
* how about : first query every 2 adjacent pairs, so [1,2],[3,4], [5,6]. then, discard the ones that return true.
* that effectively splits the sequence into many segments. notice how in the extreme case, we get only 2 segments:
* ((())) -> (( ; )). but then we can break this down again. but how? i don't think we can break this down more.
* what if instead of grouping like that, we query from the center each time? that way we can keep decomposing the problem right?
* so like ((())) -> solved in first pass because every bracket pair matches. let's consider extreme case:
* ()()(). -> ) ( -> query 2..5 -> solved.
* i *think* that may work! in fact, let's consider the information theory aspect. in the AC solution every query must give us 1
* information. since in the valid subtask we already have a significant piece of info, i think that gives us at least 2x the info
* which would suggest we can solve it in N/2 queries.
* let's consider more extreme cases.
* ()()()() . -> ))(( -> no -> no. i think that works. let's go ahead with the implementation.
*
* so we need some sort of recursive function that can keep decomposing the string.
* say we start with just one full string, s. then we query
* [1, n], [2,n-1], ... , ...
* every time query is true, we just give () to the endpoints in the answer.
* but if query is false, then we need to keep these 2 points. we will need to somehow give these to the next recursive function.
* so say n=8, string is ()()()(). then we have
* [2, 7]: )( - false. [4,5]: )( - false. then we need to deal with these two.
* say we sort the subarray of all the indices who need merging. then: [2,4,5,7]. we can then take [4,5] and [2,7] and go again.
* but special case: [4,5] is adjacent so we can just mark it as )(. why? otherwise, they would be paired with someone else, i think,
* and won't appear here. wait, is this true? i'm doubtful. you know what, let's assume this is true for a valid sequence, which
* _feels_ correct. then the problem is reduced as we only have [2, 7] left. but is this always going to happen? unsure. i think it is.
* because every time, for the center pair, if it's false then we give )(, if it's true then we give (), sooner or later it's going to be reduced.
* ehhh, let's try this first. i have no idea if it works.
* so how does the dp work? say we give it an vector of indices. then it outputs, for each index, if the char is true or false. i think that works.
* so input: vector<int>, output: vector<char>, then after we get the output from the child function, we update it in the original vector accordingly.
* isn't that O(N^2)? well we can worry about that later, first let's check if this is correct.
*/
#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}];
}
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;
}
// dfs recursively
void dfs(const vector<int>& input, vector<char>& output) {
int sz = input.size();
vector<int> next_it; // elements for next iteration
for (int i = 1; i <= sz/2; i++) {
int j = sz-i;
int q = query(i,j, input);
if (q == 1) {
output[i] = '(';
output[j] = ')';
}
else {
if (i == sz/2) {
// special case:
output[i] = ')';
output[j] = '(';
}
else {
next_it.push_back(i);
next_it.push_back(j);
}
}
}
if (next_it.empty()) {
return;
}
// sort
sort(next_it.begin(), next_it.end());
vector<char> new_output(next_it.size());
dfs(next_it, new_output);
// assign output
for (int j = 0; j < sz; j++) {
if (new_output[j]) {
output[next_it[j]] = new_output[j];
}
}
}
int main() {
cin >> n >> q;
vector<int> in(n+1);
for (int i = 1; i <= n; i++) in[i] = i;
vector<char> out(n+1);
dfs(in, out);
output(out);
}
