A. Streets of Working Lanterns - 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Policeman Anatoliy again monitors a lair of unorganized criminal group spreading prohibited Asian drawings. Presently the criminals are also sharing wireless Internet which can be used anonymously by whoever wants to. The lair still has only one entrance, which is also an exit. When someone enters into the lair, Anatoliy writes an opening round bracket in his notepad, and when someone comes out, he writes a closing round bracket.

Anatoliy decided to refrain from eating donuts in order not to spoil the records just like the previous time, but nevertheless, when he tore a sheet out of a notepad to file it to a criminal case, accidentally tore it into pieces. He doesn't want his boss to shout on him, so he must restore his records by connecting pieces in the right order. It's good for him that the layout of notepad sheets allows to determine where top and bottom sides of these pieces are. Anatoliy ensured that the lair of criminals was empty before he started the surveillance and after he ended it.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of pieces of paper with opening and closing round brackets written on them.

The next n lines contain only characters «(» and «)» — these are the strings written on pieces. The total number of brackets does not exceed 2·105.

Output

If the given pieces can be connected so that the resulting string does not contradict the statement, output in the first line «YES» without quotes. In the second line output n integers separated by spaces — the numbers of pieces in the order they must be connected. The pieces are numbered from one in the order they are mentioned in the input.

If Anatoliy messed up something and the given pieces cannot form the correct record, output in the only line «NO» without quotes.

Examples
Input
3
(
()
)
Output
YES
1 2 3
Input
3
)))
((
(
Output
YES
2 3 1
Input
3
)))
((
)
Output
NO