Sereja has a bracket sequence s_1, s_2, ..., s_{n}, or, in other words, a string s of length n, consisting of characters "(" and ")".

Sereja needs to answer m queries, each of them is described by two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence s_{l}_{i}, s_{l}_{i} + 1, ..., s_{r}_{i}. Help Sereja answer all queries.

You can find the definitions for a subsequence and a correct bracket sequence in the notes.


-----Input-----

The first line contains a sequence of characters s_1, s_2, ..., s_{n} (1 ≤ n ≤ 10^6) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 10^5) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the description of the i-th query.


-----Output-----

Print the answer to each question on a single line. Print the answers in the order they go in the input.


-----Examples-----
Input
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Output
0
0
2
10
4
6
6



-----Note-----

A subsequence of length |x| of string s = s_1s_2... s_{|}s| (where |s| is the length of string s) is string x = s_{k}_1s_{k}_2... s_{k}_{|}x| (1 ≤ k_1 < k_2 < ... < k_{|}x| ≤ |s|).

A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

For the third query required sequence will be «()».

For the fourth query required sequence will be «()(())(())».

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import os, sys
from io import BytesIO, IOBase
from array import array

def construct(n, x, si):
	left = array('i', [0] * (si << 1))
	right = array('i', [0] * (si << 1))
	tree = array('i', [0] * (si << 1))
	for i in range(si, si + n):
		if x[i - si] == '(':
			left[i] = 1
		else:
			right[i] = 1
	(a, b) = (si >> 1, si)
	while a:
		for i in range(a, b):
			z = min(left[i << 1], right[i << 1 | 1])
			tree[i] = tree[i << 1] + tree[i << 1 | 1] + 2 * z
			left[i] = left[i << 1] + left[i << 1 | 1] - z
			right[i] = right[i << 1] + right[i << 1 | 1] - z
		(a, b) = (a >> 1, b >> 1)
	return (left, right, tree)

def query(tree, left, right, l, r, si):
	(l, r) = (l + si - 1, r + si - 1)
	(partl, partr) = ([], [])
	while l < r:
		if l & 1:
			partl.append(l)
			l += 1
		if not r & 1:
			partr.append(r)
			r -= 1
		(l, r) = (l >> 1, r >> 1)
	if l == r:
		partl.append(l)
	(ans, le) = (0, 0)
	for i in partl + partr[::-1]:
		tk = min(le, right[i])
		ans += 2 * tk + tree[i]
		le += left[i] - tk
	return ans

def main():
	s = input().strip()
	n = len(s)
	si = 1 << n.bit_length() - (not n & n - 1)
	(left, right, tree) = construct(n, s, si)
	for _ in range(int(input())):
		(l, r) = map(int, input().split())
		print(query(tree, left, right, l, r, si))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
s = input().strip()
n = len(s)

class segTree:

	def __init__(self):
		self.a = [0] * (2 * n)
		self.b = [0] * (2 * n)
		self.c = [0] * (2 * n)

	def build(self, arr):
		for i in range(n):
			self.a[i + n] = 0
			self.b[i + n] = 1 if arr[i] == '(' else 0
			self.c[i + n] = 1 if arr[i] == ')' else 0
		for i in range(n - 1, 0, -1):
			to_match = min(self.b[i << 1], self.c[i << 1 | 1])
			self.a[i] = self.a[i << 1] + self.a[i << 1 | 1] + 2 * to_match
			self.b[i] = self.b[i << 1] + self.b[i << 1 | 1] - to_match
			self.c[i] = self.c[i << 1] + self.c[i << 1 | 1] - to_match

	def query(self, l, r):
		left = []
		right = []
		l += n
		r += n
		while l <= r:
			if l & 1:
				left.append((self.a[l], self.b[l], self.c[l]))
				l += 1
			if not r & 1:
				right.append((self.a[r], self.b[r], self.c[r]))
				r -= 1
			l >>= 1
			r >>= 1
		a1 = b1 = c1 = 0
		for (a2, b2, c2) in left + right[::-1]:
			to_match = min(b1, c2)
			a1 += a2 + 2 * to_match
			b1 += b2 - to_match
			c1 += c2 - to_match
		return a1
tree = segTree()
tree.build(s)
for m in range(getInt()):
	(l, r) = zzz()
	l -= 1
	r -= 1
	print(tree.query(l, r))


import sys
import math
input = sys.stdin.readline
s = input().rstrip()
n = len(s)
q = int(input())

class segTree:

	def __init__(self):
		self.a = [0] * (2 * n)
		self.b = [0] * (2 * n)
		self.c = [0] * (2 * n)

	def build(self, arr):
		for i in range(n):
			self.a[i + n] = 0
			self.b[i + n] = 1 if arr[i] == '(' else 0
			self.c[i + n] = 1 if arr[i] == ')' else 0
		for i in range(n - 1, 0, -1):
			t = min(self.b[i << 1], self.c[i << 1 | 1])
			self.a[i] = self.a[i << 1] + self.a[i << 1 | 1] + 2 * t
			self.b[i] = self.b[i << 1] + self.b[i << 1 | 1] - t
			self.c[i] = self.c[i << 1] + self.c[i << 1 | 1] - t

	def query(self, l, r):
		left = []
		right = []
		l += n
		r += n
		while l <= r:
			if l & 1:
				left.append([self.a[l], self.b[l], self.c[l]])
				l += 1
			if not r & 1:
				right.append([self.a[r], self.b[r], self.c[r]])
				r -= 1
			l >>= 1
			r >>= 1
		a1 = b1 = c1 = 0
		for (a2, b2, c2) in left + right[::-1]:
			t = min(b1, c2)
			a1 += a2 + 2 * t
			b1 += b2 - t
			c1 += c2 - t
		return a1
tr = segTree()
tr.build(s)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(tr.query(l - 1, r - 1))


import sys
input = sys.stdin.readline
s = input()
M = int(input())

def next_pow_2(n):
	p = 1
	while p < n:
		p <<= 1
	return p

def represented_range(node, size):
	l = node
	r = node
	while l < size:
		l = 2 * l
		r = 2 * r + 1
	return (l - size, r - size)

class SegTree:

	def __init__(self, size):
		self.size = next_pow_2(size)
		self.answer = [0] * (2 * self.size)
		self.opened = [0] * (2 * self.size)
		self.closed = [0] * (2 * self.size)

	def build(self, s):
		for i in range(self.size):
			self.answer[self.size + i] = 0
			self.opened[self.size + i] = 1 if i < len(s) and s[i] == '(' else 0
			self.closed[self.size + i] = 1 if i < len(s) and s[i] == ')' else 0
		for i in range(self.size - 1, 0, -1):
			matched = min(self.opened[2 * i], self.closed[2 * i + 1])
			self.answer[i] = self.answer[2 * i] + self.answer[2 * i + 1] + matched
			self.opened[i] = self.opened[2 * i] + self.opened[2 * i + 1] - matched
			self.closed[i] = self.closed[2 * i] + self.closed[2 * i + 1] - matched

	def query(self, l, r):
		l += self.size
		r += self.size
		eventsL = []
		eventsR = []
		while l <= r:
			if l & 1:
				eventsL.append((self.answer[l], self.opened[l], self.closed[l]))
				l += 1
			if not r & 1:
				eventsR.append((self.answer[r], self.opened[r], self.closed[r]))
				r -= 1
			l >>= 1
			r >>= 1
		answer = 0
		opened = 0
		for (a, o, c) in eventsL + eventsR[::-1]:
			matched = min(c, opened)
			answer += a + matched
			opened += o - matched
		return answer
seg = SegTree(len(s))
seg.build(s)
for i in range(M):
	(l, r) = [int(_) for _ in input().split()]
	print(2 * seg.query(l - 1, r - 1))


import sys, math
input = sys.stdin.readline
S = input().strip()
two_pows = set()
n = len(S)
M = int(input())

class segTree:

	def __init__(self):
		self.a = [0] * (2 * n)
		self.b = [0] * (2 * n)
		self.c = [0] * (2 * n)

	def build(self, arr):
		for i in range(n):
			self.a[i + n] = 0
			self.b[i + n] = 1 if arr[i] == '(' else 0
			self.c[i + n] = 1 if arr[i] == ')' else 0
		for i in range(n - 1, 0, -1):
			to_match = min(self.b[i << 1], self.c[i << 1 | 1])
			self.a[i] = self.a[i << 1] + self.a[i << 1 | 1] + 2 * to_match
			self.b[i] = self.b[i << 1] + self.b[i << 1 | 1] - to_match
			self.c[i] = self.c[i << 1] + self.c[i << 1 | 1] - to_match

	def query(self, l, r):
		left = []
		right = []
		l += n
		r += n
		while l <= r:
			if l & 1:
				left.append((self.a[l], self.b[l], self.c[l]))
				l += 1
			if not r & 1:
				right.append((self.a[r], self.b[r], self.c[r]))
				r -= 1
			l >>= 1
			r >>= 1
		a1 = b1 = c1 = 0
		for (a2, b2, c2) in left + right[::-1]:
			to_match = min(b1, c2)
			a1 += a2 + 2 * to_match
			b1 += b2 - to_match
			c1 += c2 - to_match
		return a1
tree = segTree()
tree.build(S)
for m in range(M):
	(l, r) = [int(s) for s in input().split()]
	l -= 1
	r -= 1
	print(tree.query(l, r))


import sys
input = sys.stdin.readline
s = input()
n = len(s)
tree = [0] * (2 * n)
closed = [0] * (2 * n)
opened = [0] * (2 * n)

def build(arr):
	for i in range(n):
		tree[n + i] = 0
		closed[i + n] = int(s[i] == ')')
		opened[i + n] = int(s[i] == '(')
	for i in range(n - 1, 0, -1):
		to_add = min(closed[i << 1 | 1], opened[i << 1])
		tree[i] = tree[i << 1] + tree[i << 1 | 1] + 2 * to_add
		closed[i] = closed[i << 1] + closed[i << 1 | 1] - to_add
		opened[i] = opened[i << 1] + opened[i << 1 | 1] - to_add

def query(l, r):
	left = []
	right = []
	l += n
	r += n
	while l <= r:
		if l & 1:
			left.append((tree[l], opened[l], closed[l]))
			l += 1
		if not r & 1:
			right.append((tree[r], opened[r], closed[r]))
			r -= 1
		l >>= 1
		r >>= 1
	a1 = b1 = c1 = 0
	for (a2, b2, c2) in left + right[::-1]:
		to_match = min(b1, c2)
		a1 += a2 + 2 * to_match
		b1 += b2 - to_match
		c1 += c2 - to_match
	return a1
build(s)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(query(a - 1, b - 1))