给定一棵二叉树，其中每个节点的值只能是 $0$ 或 $1$。从根节点到任意叶子节点的一条路径，都可以按照从上到下的顺序组成一个二进制数。

例如路径 $1\to0\to1$ 表示二进制数 $101$。请把所有根到叶路径表示的二进制数相加，并输出它们的十进制总和。

输入格式

第一行一个整数 $n$，表示二叉树的节点数。节点编号为 $1$ 到 $n$，根节点编号为 $1$；当 $n=0$ 时表示空树。

当 $n>0$ 时，第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示节点 $i$ 保存的值。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子编号和右孩子编号。编号 $0$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

输出格式

输出一个整数，表示所有根到叶路径对应的二进制数之和。

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

8

1
1
0 0

1

2
1 0
0 2
0 0

2

数据范围与约定

• 树中的节点数在 [1, 1000] 范围内
• v_i 仅为 0 或 1