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.