Sereja và dãy ngoặc (Sereja and Brackets)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Cho chuỗi ngoặc $S$ độ dài $N$, chỉ gồm ( và ). Với mỗi truy vấn $[l,r]$, hãy tìm độ dài lớn nhất của một dãy con đúng (không nhất thiết liên tiếp) lấy từ $S_lS_{l+1}\ldots S_r$.

Một dãy ngoặc đúng là dãy có thể ghép cặp các ngoặc theo đúng thứ tự mở trước, đóng sau và mọi ngoặc đều thuộc một cặp.

Input

Dòng đầu chứa chuỗi $S$, $1\le N\le 10^6$.

Dòng thứ hai chứa $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa $l,r$.

Output

Với mỗi truy vấn, in độ dài lớn nhất của dãy ngoặc con đúng.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$.
• Subtask 2 — 30%: $1\le N\le 5000$, $1\le Q\le 5000$.
• Subtask 3 — 50%: $1\le N\le 10^6$, $1\le Q\le 10^5$.

Ví dụ

Input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Output

0
0
2
10
4
6
6

Giải thích

Mỗi kết quả là độ dài chẵn vì một dãy ngoặc đúng gồm các cặp ngoặc. Truy vấn $[1,12]$ lấy được dãy con đúng độ dài $10$.