Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Given a set of N nodes, where each node has a character A[i] associated with it. A[i] can be either an opening bracket ( or a closing bracket ). Construct a tree using N nodes numbered 1 to N such that the value of the given function Z is maximized.

\(Z = \sum_\limits{i = 1}^{i = N} [\sum_\limits{j = i + 1}^{j = N}[F(i,j)]]\), where \(F(i,j)\) = Length of the longest balanced parenthesis substring on the simple path between node i and node j.

A string is said to be balanced if

Empty string is a balanced string.
if \(s\) is a balanced string, then \((s)\) is also a balanced string.
if \(s\) and \(t\) are balanced strings, then \(st\) (concatenation of \(s\) and \(t\)) is also a balanced string.

For example : (())) is not balanced as last closing bracket is unmatched.

Input format

The first line contains an integer N denoting the number of nodes in the tree.
The next line contains a string \(A\) of length \(N\) where each character denotes the value of each node i.e. A[i].

Output format

Print N - 1 lines where each line contains
- Two space-separated integers a, b denote an edge between nodes a and b in the tree.

Constraints

\(2 \le N \le 500 \)

Verdict and Scoring

Z is the score for each test case.
If the output is not a tree or contains any invalid entry, then you will receive a Wrong Answer verdict.