C. Сережа болон Хаалт

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережад $n$ урттай $s$ тэмдэгт мөр өгөгдсөн. Тэмдэгт бүр нь $(,)$ хоёр тэмдэгтийн аль нэг нь байна.

Сережад $m$ ширхэг хүсэлт ирсэн. Хүсэлт бүр $l_i, r_i (1 ≤ l_i ≤ r_i ≤ n)$ гэсэн хоёр тооноос тогтоно. $i$-р хүсэлтийн хариу нь $ s_{l_i}, s_{{l_i} + 1}, ..., s_{r_i}$ энэ завсар дахь хамгийн урт зөв хаалтыг олох юм. Сережад хүсэлтүүдэд хариу өгөхөд нь туслана уу.

Та доорх тэмдэглэлээс зөв хаалтны тодорхойлолтыг харж болно.

Жишээлбэл "(())(" тэмдэгт мөр өгөгдсөн гэж үзвэл:

  • l = 1, r = 1 үед "(" зөв хаалт болж чадахгүй учраас хариу = 0
  • l = 2, r = 3 үед "()" зөв хаалт учраас хариу = 2
  • l = 1, r = 5 үед "(())(" эндээс хамгийн урт зөв хаалт нь "(())" болно. Тэгээд хариу = 4

Оролт

Эхний мөрөнд $n(1 ≤ n ≤ 10^6)$ урттай $s$ тэмдэгт мөр өгөгдөнө. Хоёр дахь мөрөнд хүсэлтийн тоо $m (1 ≤ m ≤ 10^5)$ өгөгдөнө. Дараагийн $m$ мөр бүрт $ l_i, r_i (1 ≤ l_i ≤ r_i ≤ n)$ хоёр тоо өгөгдөнө.

Гаралт

Хүсэлт бүрийн хариуг нэг нэг мөрөнд хэвлэнэ.

Орчуулсан: Хүрэлцоож

Жишээ тэстүүд

Оролт
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
Гаралт
0
0
2
10
4
6
6

Тэмдэглэл

A subsequence$ of length $|x|$ of string $s = s_{1}s_{2}... s_{|s|}$ (where $|s|$ is the length of string $s$) is string $x = s_{k_{1}}s_{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 «()(())(())$».

Сэтгэгдлүүдийг ачааллаж байна...