A remote monitoring network is organized as a rooted binary tree of stations. Every leaf station is a raw sensor that independently reports either all-clear (encoded as 0) or alert (encoded as 1). Every non-leaf station is a fusion relay with exactly two child stations, and combines their reports using one of two fixed rules built into the relay:

• rule 2 ("escalate-any"): the relay reports alert if at least one child reports alert (logical OR).
• rule 3 ("escalate-both"): the relay reports alert if both children report alert (logical AND).

Given the full structure of the tree, determine what the root station ultimately reports.

Input format

The first line contains a single integer n, the number of stations. Stations are numbered 1 to n, and station 1 is always the root. Each of the next n lines describes one station with three integers val left right:

• if val is 0 or 1, the station is a leaf and left = right = 0.
• if val is 2 or 3, the station is a relay and left and right are the (distinct, non-zero) indices of its two child stations.

Output format

Print a single integer: 1 if the root ultimately reports alert, 0 if it reports all-clear.

Constraints

• 1 <= n <= 10^4
• n is always odd, and the described structure always forms a valid full binary tree (every station has exactly 0 or 2 children) rooted at station 1.

3
3 2 3
1 0 0
0 0 0

0

5
2 2 5
3 3 4
1 0 0
0 0 0
1 0 0

1