Problem Description

Today, Kile is celebrating his birthday. His best friend Ivan decided to give him a special balance scale. The special feature of this scale is that it is recursive: at the end of each beam, there is either a weight, a new balance scale, or nothing. Of course, if the total mass on the left beam of a scale is greater than the total mass on the right beam, the scale will tilt to the left. Similarly, if the mass on the right beam is greater, the scale will tilt to the right. Otherwise, we say the scale is balanced. Note that this is different from the balance condition of a normal scale that we usually know. The figure below shows an example of such a scale.

Kile really likes this gift. As a true computer scientist, he immediately tries to balance it by adding new weights whose total mass is as small as possible. The weights to be added should have positive real masses. If a scale itself is balanced, and all of its sub-scales are balanced, then we say this scale is balanced.

After successfully balancing the scale, Kile decides to tattoo on his chest the total mass of all weights on the scale, written in binary without leading zeros. It can be proven that the total mass must be a positive integer. We want to know the number Kile tattoos, that is, the binary representation of the total mass of all weights on the scale after balancing it by adding new weights with the smallest possible total mass.

Input Format

The first line contains an integer $N$, the number of sub-scales contained in the whole structure. The root scale is numbered $1$.
Then follow $N$ lines. In line $i$, there are two integers $a, b$:

• If $a$ is positive, it means the left end of scale $i$ is a scale; otherwise, it means the left end of scale $i$ is a weight with mass $-a$.
• If $b$ is positive, it means the right end of scale $i$ is a scale; otherwise, it means the right end of scale $i$ is a weight with mass $-b$.

Output Format

Output one line: the binary representation of the total mass of all weights on the scale after balancing it by adding new weights with the smallest possible total mass. Do not include leading zeros.

2
2 -10
-4 -3

10100

4
2 3
-9 4
-2 -13
-1 -7

111000

Hint

Sample 1 Explanation

The initial state of the scale is shown in the picture in the description. Kile will place a weight of mass $1$ on the left side of scale $2$, and a weight of mass $2$ on the right side. Then both scales are balanced, and it can be proven that this plan adds the minimum possible total mass of new weights. The total mass of all weights on the scale is $5 + 5 + 10 = 20$, and its binary representation is $10100$.

Constraints

For all testdata, $1 \leqslant N \leqslant 10^6$, $-10^9 \leqslant a, b \leqslant N$.

Source

This problem comes from COCI 2016-2017 CONTEST 7 T4 POKLON, and follows the original testdata configuration, with a full score of $120$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5