The Astral Express is a special train that traverses the galaxy. The galaxy initially consists of $$$2 \cdot n$$$ planets represented as an array $$$a_1, a_2, \ldots, a_{2 \cdot n}$$$, where the $$$i$$$-th planet initially has a gravitational coefficient of $$$a_i = 1$$$ if $$$i \le n$$$ and $$$a_i = -1$$$ if $$$i \gt n$$$.

The Astral Express moves in steps, and the direction of the movement is determined by its velocity $$$v$$$. At the beginning of each step, if $$$v \gt 0$$$, then the Express moves one index to the right. If $$$v \lt 0$$$, then the Express moves one index to the left. If $$$v = 0$$$, then the crew moves in the direction they moved previously. At the end of each step, if the Express is at position $$$i$$$, then $$$a_i$$$ is added to $$$v$$$. If the Astral Express goes past the bounds of the array, then its journey will end.

Since the galaxy is unstable, the planets are constantly breaking apart and merging. A planet with $$$|a_i| = 2$$$ may split into two adjacent planets with gravitational coefficients of $$$\frac{a_i}{2}$$$, and two identical adjacent planets with $$$a_i = a_{i + 1}$$$ and $$$|a_i|= 1$$$ may merge into a single planet with gravitational coefficient $$$a_i + a_{i + 1}$$$.

The Astral Express crew is curious about how their train will move in this unstable galaxy, so you are given $$$q$$$ queries of $$$3$$$ types:

• "1 x" — The Astral Express begins moving at the rightmost positive $$$a_i$$$ with their given initial velocity equal to $$$x$$$. Output how many steps the Astral Express will take before their journey ends, or output $$$-1$$$ if their journey will go on forever.
• "2 x" — Merge $$$a_x$$$ and $$$a_{x + 1}$$$ into a new planet with gravitational coefficient $$$a_x + a_{x + 1}$$$. Formally, set $$$a_x$$$ to $$$a_x + a_{x + 1}$$$, and remove $$$a_{x + 1}$$$ from the array. Note that the indices of all elements right of $$$a_{x + 1}$$$ will decrease by one. It is guaranteed that $$$a_x = a_{x + 1}$$$ and $$$|a_x| = 1$$$.
• "3 x" — Split $$$a_x$$$ into two new planets both with gravitational coefficients $$$\frac{a_x}{2}$$$. Formally, set $$$a_x$$$ to $$$\frac{a_x}{2}$$$ and insert a new planet with gravitational coefficient $$$a_x$$$ at index $$$x + 1$$$. Note that the indices to the right of the inserted element will increase by one. It is guaranteed that $$$|a_x| = 2$$$.

For example, given $$$n = 3$$$, our initial array will look like $$$[1, 1, 1, -1, -1, -1]$$$, and we can perform an operation "2 2", merging $$$a_2$$$ and $$$a_3$$$ together, resulting in an array of $$$[1, 2, -1, -1, -1]$$$. We can then perform an operation "3 2", splitting $$$a_2$$$ into two elements, resulting in an array of $$$[1, 1, 1, -1, -1, -1]$$$.