File Paths

Byteasar likes to live risky. He runs with scissors, submits contest solutions without trying them on the example input, and wants every one of his files to have a path name exactly as long as the operating system allows. On Linux that length is 4095 characters.

When he works on someone else's computer, some files do not meet that criterion. In that case he creates one symbolic link and builds new path names with it. For each file in the file system, decide whether he can create a single symbolic link, whose name length he fixes in advance, so that the file can be referred to by a path name of length exactly $k$.

If a file named file sits inside the chain of directories dir1, dir2, ..., dirj, its absolute path is /dir1/dir2/.../dirj/file. The root directory is referred to as /, and a file contained directly in the root has an absolute path of the form /file.

A symbolic link is a named shortcut to a directory and can be placed in any directory of the file system. In this problem symbolic links to files are not allowed. A symbolic link gives alternative paths to the same file. For example, with a link named hello in / that points to /, the paths /dir/file, /hello/dir/file and /hello/hello/dir/file all refer to the same file and differ only in length. With a link named hi in /dir that points to /, you get /dir/file, /dir/hi/dir/file and /dir/hi/dir/hi/dir/file. A link may point upwards, downwards or sidewards in the hierarchy, and even back at the directory that holds it. The components ./, ../ and // are not allowed in path names.

The first line contains three positive integers $n$, $m$ and $k$: the number of directories other than the root, the number of files, and the desired path name length. The root directory has number 0, the remaining directories are numbered 1 through $n$, and the files are numbered 1 through $m$.

The second line contains the length $s$ of the symbolic link name. The name itself does not matter, and it collides with nothing else in the file system.

Then follow $n$ lines describing the directories other than the root. The $i$-th of them contains two integers $p_i$ and $l_i$: directory $i$ has a name of length $l_i$, and the directory that directly contains it has number $p_i$.

Finally $m$ lines describe the files. The $j$-th of them contains two integers $p_j$ and $l_j$: file $j$ has a name of length $l_j$ and sits in directory $p_j$.

Print $m$ lines, one per file. On line $j$ print YES if a single symbolic link of length $s$ makes it possible to refer to file $j$ by a path name of length exactly $k$, and NO otherwise.

• $1 \le n, m \le 3000$
• $1 \le k, s \le 10^6$
• $0 \le p_i < i$
• $0 \le p_j \le n$
• Every file name and directory name has positive length, and every absolute path is at most $k$ characters long.

The first example describes the file system below. Call the symbolic link LL, the directory names a and bbbbb, and the file names ccccccccccccc, dddddddddd, eeee and fffffff in that order. The root holds the directory a and the file fffffff, the directory a holds the directory bbbbb and the file eeee, and bbbbb holds the files ccccccccccccc and dddddddddd.

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

For file 1 the absolute path /a/bbbbb/ccccccccccccc already has length 22, so no link is needed. For file 2, put the link LL in /a pointing to /a and use /a/LL/bbbbb/dddddddddd. For file 3, put the link LL in /a pointing to / and use /a/LL/a/LL/a/LL/a/eeee. For file 4 no placement of the link reaches length 22.