给定一棵二叉树和一个整数 $T$，请判断树中是否存在一条从根节点到叶子节点的路径，使路径上所有节点值的总和恰好等于 $T$。

路径必须从根开始，并在一个没有任何孩子的叶子节点结束，不能在普通内部节点提前停止。空树不存在满足条件的根到叶路径。

输入格式

第一行一个整数 $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$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

最后一行输入一个整数 $T$，表示目标路径和。

输出格式

如果存在满足条件的根到叶路径，输出 true；否则输出 false。

2
2 10
2 0
0 0
12

true

3
-2 -3 -4
0 2
3 0
0 0
1000

false

5
-7 -4 2 1 7
2 3
4 0
0 5
0 0
0 0
2

true

数据范围与约定

• 树中节点的数目在范围 [0, 5000] 内
• -1000 ≤ v_i ≤ 1000
• -1000 ≤ targetSum ≤ 1000