B'This is the hard version of the problem. The only difference between the easy and the hard versions are removal queries, they are present only in the hard version. "Interplanetary Software, Inc." together with "Robots of Cydonia, Ltd." has developed and released robot cats. These electronic pets can meow, catch mice and entertain the owner in various ways. The developers from "Interplanetary Software, Inc." have recently decided to release a software update for these robots. After the update, the cats must solve the problems about bracket sequences. One of the problems is described below. First, we need to learn a bit of bracket sequence theory. Consider the strings that contain characters "(", ")" and ".". Call a string regular bracket sequence (RBS), if it can be transformed to an empty string by one or more operations of removing either single "." characters, or a continuous substring "()". For instance, the string "(()(.))" is an RBS, as it can be transformed to an empty string with the following sequence of removals: We got an empty string, so the initial string was an RBS. At the same time, the string ")(" is not an RBS, as it is not possible to apply such removal operations to it. An RBS is simple if this RBS is not empty, doesn 't start with ".", and doesn 't end with ".". Denote the substring of the string s as its sequential subsegment. In particular, s[l ... r] = s_ls_{l+1} ... s_r , where s_i is the i -th character of the string s . Now, move on to the problem statement itself. You are given a string s , initially consisting of characters "(" and ")". You need to answer the following queries: You are an employee in "Interplanetary Software, Inc." and you were given the task to teach the cats to solve the problem above, after the update. The first line contains two integers n and q ( 2 <= n <= 3 cdot10^5 , 1 <= q <= 3 cdot10^5 ), the length of the string, and the number of queries. The sec'...