M. Magical Book
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As the manager of the magical library of the Yuugyuuji's, Chrysoberyl can extract any contiguous subsequence from an existing magical book to create a new tome. The magical books are composed solely of parentheses "(" and ")". A book is considered beautiful if its content strictly adheres to the following formal grammar:

  • The atomic unit $$$\mathtt{()}$$$ is beautiful.
  • For any beautiful book $$$A$$$, the wrapped form $$$\mathtt{(}A\mathtt{)}$$$ is also beautiful.
  • For any two beautiful books $$$A$$$ and $$$B$$$, their concatenation $$$AB$$$ preserves its beauty.

Chrysoberyl possesses $$$q$$$ identical old magical books. Due to the ancient nature of these books, their opening and closing sections have become unusable. Specifically, for the $$$i$$$-th book, she must select a substring between positions $$$l_i$$$ and $$$r_i$$$ (inclusive). Two selection methods are considered different if and only if they have distinct starting positions or distinct ending positions, even if their content is identical.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n$$$, $$$q\le 2\cdot10^5$$$) — the length of each magical book's content and the number of the magical books.

The second line contains $$$n$$$ characters $$$s_1,s_2,\dots,s_n$$$ ($$$s_i=\mathtt{'('}$$$ or $$$\mathtt{')'}$$$) — each magical book's content.

Each of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$).

Output

Output $$$q$$$ integers. The $$$i$$$-th integer represents the number of different ways that Chrysoberyl can create a beautiful book from the $$$i$$$-th book.

Example
Input
12 7
())(())(())(
1 1
2 3
1 2
1 12
8 12
5 11
2 10
Output
0 0 1 6 2 3 3