You work in a company that provides consulting services, and a customer has asked your company to design a concise way of representing all valid parenthesis expressions of even length n. Recall that valid parenthesis expressions are defined as follows:

• () is a valid parenthesis expression;
• (S) is a valid parenthesis expression if S is a valid parenthesis expression; and
• ST is a valid parenthesis expression if S and T are valid parenthesis expressions.

Your colleague suggests an approach for enumerating the expressions by starting from a valid parenthesis expression of length n and then flipping two parentheses on each iteration to obtain a new one. Except for the first parenthesis expression, the expressions can then be encoded by outputting the two indices describing where the changes occur relative to the previous expression. It can be shown that all parenthesis expressions of length n can be enumerated in this way without generating any of them twice; can you construct such a sequence of parenthesis expressions?

Input

The only line of the input contains a single integer n.

Output

On the first line of the output, output your starting parenthesis expression.

On the consecutive lines, output two integers describing the indices of the parentheses to be flipped.

Constraints

• 2 \le n \le 20
• n is even

Example

Input:

6

Output:

((()))
3 4
2 3
4 5
2 3

Explanation: The operations correspond to the following parenthesis sequences:

((()))
(()())
()(())
()()()
(())()