406104: GYM102267 I Ultimate Army

3 days, that's how much time the king gave Daffy to find him the ultimate army organization plan before he cuts his head off.

2 days already passed with no progress, but luckily Bugs came to the rescue, he gave Daffy the "ultimate"{} plan as a string, unfortunately Daffy couldn't understand this string, now only 4 hours remain.

A soldier can be described in Bugs's string as this: first the $$$id$$$ of the soldier is written then following it $$$x$$$ brackets $$$()$$$ each for a subordinate of this soldier, each subordinate is described inside their bracket in the same way, for example the following string "$$$2(3(4))(1)$$$"{} means that soldier $$$2$$$ is the supervisor of soldiers $$$3$$$ and $$$1$$$, and soldier $$$3$$$ is the supervisor of soldier $$$4$$$, while soldiers $$$1$$$ and $$$4$$$ doesn't supervise any soldiers. The string Bugs gave you describes the king(he has no supervisor) and his subordinates and their subordinates and so on.

Or more formally: $$$$$$ Soldier = Id+Subordinates$$$$$$ $$$$$$ Subordinates = (Soldier)+Subordinates | \phi$$$$$$ where $$$\phi$$$ is the empty string.

Can you figure out the supervisor of each soldier and save Daffy's head?

In the first line you're given an integer $$$n$$$($$$1 \le n \le 1.4 \times 10^5$$$), the number of soldiers(including the king) in the army.

In the second line you're given Bugs's string as described above, the string's length is less than or equal to $$$10^6$$$.

It's guaranteed that each $$$id$$$ from $$$1$$$ to $$$n$$$ appears exactly once in the string.

Output in a single line $$$n$$$ space separated integers, the $$$i$$$th of these integers is the supervisor of the $$$i$$$th soldier or $$$0$$$ if this soldier has no supervisor(he's the king, notice that there will be only one such soldier).

4
2(3(4))(1)

2 0 2 3

7
4(2)(5(3(6)(1))(7))

3 4 5 0 4 3 5