Poklon

Kile은 생일 선물로 재귀 저울을 받았다. 이 저울의 각 팔 끝에는 추 하나가 놓여 있거나, 다른 저울 하나가 매달려 있거나, 아무것도 없다. 왼쪽 팔에 걸린 질량의 합이 오른쪽 팔에 걸린 질량의 합보다 크면 저울은 왼쪽으로 기울고, 오른쪽이 더 크면 오른쪽으로 기운다. 두 합이 같으면 그 저울은 평형이다.

Kile은 새 추를 올려서 저울을 평형으로 만들려고 한다. 새로 올리는 추의 질량은 양의 실수이고, 이미 놓인 추를 치우거나 그 질량을 바꿀 수는 없다. 저울 자신과 그 안의 모든 부분 저울이 전부 평형일 때 재귀 저울이 평형이라고 한다.

새로 올리는 추의 질량 합이 최소가 되도록 평형을 만들자. 이때 저울에 놓인 추의 질량 총합을 이진법으로 나타내면 얼마인가?

첫째 줄에 재귀 저울을 이루는 저울의 개수 $N$ ($1 \le N \le 10^6$)이 주어진다. 루트 저울도 이 개수에 포함된다.

다음 $N$개의 줄 중 $i$번째 줄에는 $i$번 저울의 왼쪽 팔과 오른쪽 팔을 설명하는 정수 두 개가 차례로 주어진다. 양수는 그 팔에 매달린 저울의 번호이고, $0$ 이하의 수는 그 팔에 추가 놓여 있다는 뜻이며 추의 질량은 그 수의 절댓값이다. 질량이 $0$이면 그 팔에는 아무것도 없다. 다른 모든 저울을 포함하는 루트 저울의 번호는 $1$이다.

입력의 모든 수는 절댓값이 $10^9$ 이하이다. $1$번을 제외한 모든 저울은 다른 저울의 팔 하나에 정확히 한 번 매달려 있으므로, 저울 전체는 $1$번을 루트로 하는 트리를 이룬다.

평형을 만든 뒤 저울에 놓인 추의 질량 총합을 이진법으로 첫째 줄에 출력한다. 앞에 $0$을 붙이지 않는다. 총합이 $0$이면 0을 출력한다.

첫 번째 예제는 위 그림과 같다. 질량이 $4$인 추가 놓인 팔에 질량 $1$인 추를 더 올리고, 질량이 $3$인 추가 놓인 팔에 질량 $2$인 추를 더 올리면 $2$번 저울의 두 팔이 모두 $5$가 되어 평형이 된다. 그러면 $1$번 저울의 두 팔은 모두 $10$이므로 $1$번 저울도 평형이다. 저울에 놓인 추의 질량 총합은 $5 + 5 + 10 = 20$이고, 이진법으로 나타내면 $10100$이다.