All correct parenthesizations P48260

Statement

Given some pairs of corresponding open and close parenthesis, we can use them to build an infinite number of correct parenthesizations. For instance, with the pairs ( ) and [ ], all correct parenthesizations are defined by the grammar $\begin{align*} P & \rightarrow \enspace <\mbox{empty word}> \\ P & \rightarrow \texttt{(} P \texttt{)} P \\ P & \rightarrow \texttt{[} P \texttt{]} P \end{align*}$

Can you generate all correct parenthesizations of a given size?

Input

Input consists of a non-empty string $s$ and a strictly positive even number $n$ . The string $s$ has even size, and includes the corresponding pairs of open and close parenthesis: $s[0]$ with $s[1]$ , $s[2]$ with $s[3]$ , etc.

Output

Print all correct parenthesizations of size $n$ that can be made up with the corresponding open and close parenthesis included in $s$ .

Observation

You can print the parenthesizations in any order.

Public test cases

Input

() 6

Output

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

Input

{}()[] 2

Output

{}
()
[]

Input

[]() 4

Output

[][]
()[]
[]()
()()
[[]]
([])
[()]
(())

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++ Haskell