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 string $S$ of length $N$ consisting of two characters (open bracket) $($ and (close bracket) $)$. We need to decompose $S$ into $K$ consecutive non-empty substrings such that every character is present in only one substring.

Say substrings are $S[1], S[2], S[3], ... , S[K]$. Choose an array $B$, which is a permutation of $1$ to $K$ i.e. it is of size $K$ and include every element from $1$ to $K$.

Also, along we can choose to keep every substring as it is or in reverse order. That means you can reverse $S[i] \; (1 \leq i \leq K)$ before form  new string $V$. 

Now, form a new string $V$ = $S[B[1]] + S[B[2]] + .... + S[B[K]]$. A matching pair of brackets is not balanced if the set of brackets it encloses are not matched.

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.

Suppose number of balanced substrings in $V$ is $X$ (of length greater than 1) and number of substrings among $S[1], S[2], S[3], ... , S[K]$ which were not reversed are $Y$.

Aim is to maximize $Z = X \times (Y + 1)$.

Input format

• First line contains two space-separated integers $N \ K$
• Next line contains a string $S$.

Output format

• In the first $K$ lines, print $2$ integers denoting end index of $i^{th}$ substring (indexes are 1 based) and whether it is reversed or not (0 for not reversed and 1 for reversed).
• In next line print $K$ space separated integers, denoting array $B$ (permutation of 1 to K)
• Note : End index of substrings should be in increasing order.

Verdict and scoring

• Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of $Z$ that you found.
• If decomposition of string $S$ is invalid, or array $B$ is invalid you will receive a wrong answer verdict.

Constraints

$N = 10^3 \\ 50 \le K \le 10^2$