Cho dãy ngoặc đúng gồm ~n~ dấu mở ngoặc ( và ~n~ dấu đóng ngoặc ). Các dấu ngoặc được đánh số thứ tự từ ~1~ đến ~2n~. Hãy liệt kê chỉ số của các cặp dấu mở ngoặc và đóng ngoặc tương ứng.

Input

• Gồm một dòng duy nhất chứa xâu ký tự biểu diễn dãy ngoặc.

Giới hạn:

• ~1 ≤ n ≤ 10^5~.

Output

• Gồm ~n~ dòng, mỗi dòng gồm hai số ~u, v~ là chỉ số của các cặp ngoặc tương ứng nhau, thứ tự liệt kê tăng dần theo chỉ số của dấu ngoặc đóng.

Sample

Input #1

()(()())

Output #1

1 2
4 5
6 7
3 8

Problem source: Chuyên Sơn La Online Judge