XCND Xâu con ngoặc đúng

Cho một dãy ngoặc độ dài N gồm 2 loại kí tự ‘(‘ và ‘)’, cho M truy vấn có dạng l_i, r_i.

Yêu cầu:với mỗi truy vấn tìm một xâu con (không cần liên tiếp) của chuỗi từ l_i đến r_i dài nhất mà tạo thành dãy ngoặc đúng.

Input

• Dòng đầu ghi xâu s có độ dài n, các kí tự là ‘(‘) hoặc ‘)’ dài không quá 10⁶ kí tự.
• Dòng thứ hai ghi số m là số truy vấn (1 ≤ m ≤ 10⁵)
• m dòng tiếp theo, dòng thứ i ghi 2 số l_i r_i mô tả truy vấn thứ i (1 ≤ l_i ≤ r_i ≤ n)

Output: với mỗi truy vấn ghi độ dài xâu con dài nhất tìm được

Input	Output	Giải thích
())(())(())( 7 1 1 2 3 1 2 1 12 8 12 5 11 2 10	0 0 2 10 4 6 6	Truy vấn cuối 2 10, cho kết quả xâu con dài nhất là 6 gồm các kí tự thứ 4, 5, 6, 7, 9, 10