入力

入力は以下の形式で標準入力から与えられます。

S

出力

|S| を S の長さと表したとき、カッコの対応を以下の形式にしたがって |S|/2 行で出力せよ。

l_1 r_1
:
l_{|S|/2} r_{|S|/2}

これは、「l_1 文字目と r_1 文字目」, ... ,「l_{|S|/2} 文字目と r_{|S|/2} 文字目」が対応していることを表します。

出力は以下の条件を満たす必要があります。

• 1 \leq l_i < r_i \leq |S| \ (1 \leq i \leq |S|/2)
• \text{max}(l_i, r_i) < \text{max}(l_{i + 1}, r_{i + 1}) \ (1 \leq i \leq |S|/2 - 1)

制約

• 1 \leq |S| \leq 200,000
• S は()の文字から構成される対応の取れたカッコ列