AT_bogosortcontest_div1_n Delete Sad Faces (Hard)

tatesoto 君は以下の問題を考えました。 > 文字 `:`, `(`, `)` からなる文字列について考えます。 隣接する $ 2 $ 文字が以下のいずれかであるとき、その $ 2 $ 文字を顔文字と呼びます。 > > - `:)`, `(:` を笑顔と呼びます。 > - `:(`, `):` を悲しい顔と呼びます。 > > 文字列 $ T $ に含まれる笑顔（悲しい顔）の個数とは、 $ 1 \le i \lt |T| $ を満たし、 $ T_iT_{i+1} $ が笑顔（悲しい顔）であるような整数 $ i $ の個数を指します。 > > 複数の顔文字が同じ文字を共有している場合も、それぞれ数えることに注意してください。例えば、文字列 `(:):` には、`(:`, `:)`, `):` が含まれるため、笑顔の個数は $ 2 $ 、悲しい顔の個数は $ 1 $ です。 > > 文字列 $ T $ が与えられます。 あなたは $ T $ に対して、以下の操作を悲しい顔が含まれなくなるまで繰り返します。 > > - 現在の文字列 $ T $ に含まれる悲しい顔を $ 1 $ つ選び、その $ 2 $ 文字を削除する。その後、残った文字を順番を変えずに詰める。 > > 最終的な文字列 $ T $ に含まれる笑顔の個数としてあり得る最大値を求めてください。 この問題は soryuusi 君には簡単すぎたので、この問題を基に次のような問題を考えました。 > `:`, `(`, `)` からなる文字列 $ S $ と $ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリでは、整数 $ L_i,R_i $ $ (1\leq L_i \leq R_i \leq |S|) $ が与えられるので、部分文字列 $ T = S_{L_i}S_{L_i+1}\cdots S_{R_i} $ に対する tatesoto 君の問題の答えを求めてください。 soryuusi 君の問題を解いてください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のクエリについて、 $ T = $ `:):(` です。 $ T $ の $ 3, 4 $ 文字目の `:(` を削除することで、 $ T = $ `:)` となります。 このときの笑顔の個数は $ 1 $ 個であり、これが最大であることが証明できます。 $ 2 $ つ目のクエリについて、 $ T = $ `(:)` です。 このとき、最初から悲しい顔は含まれず、笑顔の個数は $ 2 $ 個です。 $ 3 $ つ目のクエリについて、 $ T = $ `):(` です。 $ T $ の $ 1, 2 $ 文字目の `):` を削除することで、 $ T = $ `(` となります。 このときの笑顔の個数は $ 0 $ 個であり、これが最大であることが証明できます。 $ 4 $ つ目のクエリについて、 $ T = $ `(:):(` です。 $ T $ の $ 4, 5 $ 文字目の `:(` を削除することで、 $ T = $ `(:)` となります。 このときの笑顔の個数は $ 2 $ 個であり、これが最大であることが証明できます。 ### Constraints - $ S $ は `:`, `(`, `)` からなる文字列 - $ 1\leq |S| \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1\leq L_i \leq R_i \leq |S| $ - 入力される数値はすべて整数