Byteasar 喜欢冒险。他做事雷厉风行，在不测试样例输入的情况下就提交竞赛问题的解答，并且希望他所有的文件路径名长度都恰好等于操作系统允许的最大长度（例如在 Linux 下，这个长度是 4095 个字符）。

当 Byteasar 在别人的电脑上工作时，可能会发现并非所有的文件都满足他的标准。在这种情况下，他会尝试引入符号链接（symlinks）并利用它们来创建文件路径。对于文件系统中的每个文件，请你判断 Byteasar 是否可以引入一个单一的符号链接（其长度由他预先选定），使得该文件可以通过一个长度恰好为 $k$ 个字符的路径名来访问。

如果一个名为 file 的文件包含在目录链 dir1, dir2, ..., dirj 中，那么它的绝对文件路径为 /dir1/dir2/.../dirj/file。根目录可以表示为 /，直接包含在根目录下的每个文件其绝对路径形式为 /file。符号链接是一个指向目录的命名快捷方式，可以放置在文件系统中的任何目录中。在本题中，不允许创建指向文件的符号链接。

使用符号链接，我们可以获得替代的文件路径。例如，如果我们引入一个名为 hello 且指向 / 的符号链接并放置在 / 中，那么 /dir/file、/hello/dir/file 和 /hello/hello/dir/file 都将指向同一个文件，但具有不同的路径名长度。再举一个例子，如果我们在 /dir 中引入一个名为 hi 且指向 / 的符号链接，我们可以得到如下文件路径：/dir/file、/dir/hi/dir/file、/dir/hi/dir/hi/dir/file。注意，符号链接指向文件系统层级中的上级、下级或同级目录，甚至是它所在的目录本身，都是完全合法的。在本题中，路径名中不考虑 ./、../ 或 // 等路径组件。

输入格式

输入的第一行包含三个正整数：$n$（除根目录外的目录数量）、$m$（文件数量）和 $k$（期望的路径名长度）。根目录编号为 0，其余目录编号为 1 到 $n$。文件编号为 1 到 $m$。第二行包含引入的符号链接名称的长度 $s$（我们不关心名称本身，假设它不会与文件系统中的任何其他名称冲突）。

接下来 $n$ 行描述文件系统中存在的目录（除根目录外）。第 $i$ 行描述编号为 $i$ 的目录，包含两个整数：$p_i$ 和 $l_i$。它们表示编号为 $i$ 的目录名称长度为 $l_i$，其父目录（即直接包含第 $i$ 个目录的目录）编号为 $p_i$。保证 $p_i < i$。

最后 $m$ 行描述文件系统中的文件。第 $j$ 行描述编号为 $j$ 的文件，包含两个整数：$p_j$ 和 $l_j$。它们表示编号为 $j$ 的文件名称长度为 $l_j$，其父目录编号为 $p_j$。

所有文件和目录的名称长度均为正整数，且它们的绝对文件路径长度最多为 $k$ 个字符。

输出格式

你的程序应输出 $m$ 行，每行对应一个文件。第 $j$ 行应包含一个单词 YES 或 NO，回答以下问题：是否可以通过引入一个长度为 $s$ 的符号链接，创建一个长度恰好为 $k$ 的路径名来指向编号为 $j$ 的文件？

样例

输入 1

2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

输出 1

YES
YES
YES
NO

说明

样例解释：我们将符号链接称为 LL，目录名称分别称为 a 和 bbbbb，文件名称分别称为 ccccccccccccc、dddddddddd、eeee 和 fffffff。根目录包含目录 a 和文件 fffffff；目录 a 包含目录 bbbbb 和文件 eeee；最后，目录 bbbbb 包含文件 ccccccccccccc 和 dddddddddd。

/
|-- a
| |-- bbbbb
| | |-- ccccccccccccc
| | +-- dddddddddd
| +-- eeee
+-- fffffff

在第一种情况下，绝对文件路径 /a/bbbbb/ccccccccccccc 已经达到了期望的长度，所以我们甚至不需要使用符号链接。在第二种情况下，我们可以引入符号链接 /a/LL -> /a，并访问 /a/LL/bbbbb/dddddddddd。在第三种情况下，我们应该引入符号链接 /a/LL -> /，并访问 /a/LL/a/LL/a/LL/a/eeee。在第四种情况下，无论我们在哪里引入符号链接，都无法达到目标。

数据范围

在所有子任务中，$1 \le k, s \le 1\,000\,000$。