Sereja và dãy ngoặc

Cho một dãy ngoặc $s$ độ dài $n$, gồm các ký tự "(" và ")".

Bạn cần trả lời $m$ truy vấn. Mỗi truy vấn cho hai số nguyên $l$ và $r$ ($1\le l\le r\le n$). Với mỗi truy vấn, hãy tìm độ dài của dãy ngoặc con đúng dài nhất của đoạn $s_l,s_{l+1},\dots ,s_r$.

Một dãy con của $s$ thu được bằng cách xóa đi một số ký tự (có thể không xóa) và giữ nguyên thứ tự các ký tự còn lại.

Một dãy ngoặc đúng là dãy có thể biến thành một biểu thức số học hợp lệ bằng cách chèn thêm "1" và "+". Ví dụ, "()()" và "(())" là đúng, còn ")(" và "(" thì không.

Dữ liệu vào

• Dòng đầu chứa dãy ký tự $s_1{s}_2\dots s_n$, mỗi ký tự là "(" hoặc ")".
• Dòng thứ hai chứa số nguyên $m$, số lượng truy vấn.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$, mô tả truy vấn thứ $i$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$ theo đúng thứ tự trong dữ liệu vào.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le m\le {10}^5$
• $1\le l_i\le r_i\le n$

Ví dụ