P6000 [CEOI 2016] match

You are given a string $s$ consisting of lowercase letters. You need to construct a lexicographically smallest (assume the left parenthesis is lexicographically smaller than the right parenthesis) valid parenthesis sequence that matches this string. A string and a parenthesis sequence are defined to match as follows: first, their lengths must be equal; second, for every pair of matched left and right parentheses at positions $i,j$, it must hold that $s_i=s_j$. If there is no solution, output `-1`.

One line containing a string $s$.

One line containing a parenthesis sequence, or `-1`.

For $100\%$ of the testdata, $2\le n\le 10^5$. Translated by ChatGPT 5