Byteasar thích sống mạo hiểm. Anh chạy khi đang cầm kéo, nộp lời giải mà không thử các ví dụ, và muốn mọi tệp của mình có đường dẫn dài đúng bằng giới hạn hệ điều hành cho phép; chẳng hạn, trên Linux là \(4095\) ký tự.

Khi làm việc trên máy tính của người khác, Byteasar có thể gặp những tệp chưa đáp ứng tiêu chí đó. Anh sẽ thử thêm các liên kết tượng trưng, hay symlink, rồi dùng chúng để tạo đường dẫn. Với mỗi tệp trong hệ thống, hãy xác định liệu Byteasar có thể thêm một liên kết tượng trưng duy nhất, có độ dài tên được anh chọn trước, để tồn tại một đường dẫn dài đúng \(k\) ký tự trỏ đến tệp ấy hay không. Mỗi tệp được xét độc lập.

Nếu tệp có tên file nằm trong chuỗi thư mục dir1, dir2, ..., dirj, thì đường dẫn tuyệt đối của nó là /dir1/dir2/.../dirj/file. Thư mục gốc được biểu diễn bằng /; một tệp nằm trực tiếp trong thư mục gốc có đường dẫn tuyệt đối dạng /file.

Liên kết tượng trưng là một lối tắt có tên trỏ đến một thư mục, và có thể được đặt trong bất kỳ thư mục nào của hệ thống. Trong bài toán này, không được tạo liên kết tượng trưng trỏ đến tệp.

Nhờ liên kết tượng trưng, ta có thể tạo các đường dẫn khác nhau cùng trỏ đến một tệp. Ví dụ, nếu đặt một liên kết tên hello trỏ đến / ngay trong /, thì /dir/file, /hello/dir/file và /hello/hello/dir/file đều trỏ đến cùng một tệp nhưng có độ dài khác nhau. Tương tự, nếu đặt một liên kết tên hi trỏ đến / trong /dir, ta có các đường dẫn /dir/file, /dir/hi/dir/file và /dir/hi/dir/hi/dir/file.

Liên kết có thể trỏ lên trên, xuống dưới, sang một nhánh khác trong cây thư mục, hoặc trở lại chính thư mục chứa nó. Không được sử dụng các thành phần ./, ../ hoặc // trong đường dẫn.

Dữ liệu vào

Dòng đầu chứa ba số nguyên dương \(n,m,k\): số thư mục không kể thư mục gốc, số tệp, và độ dài đường dẫn mong muốn. Thư mục gốc mang số \(0\), các thư mục còn lại được đánh số từ \(1\) đến \(n\). Các tệp được đánh số từ \(1\) đến \(m\).

Dòng thứ hai chứa số nguyên \(s\), là độ dài tên của liên kết tượng trưng được thêm. Tên cụ thể không quan trọng; dữ liệu bảo đảm tên ấy không trùng với bất kỳ tên nào khác trong hệ thống tệp.

\(n\) dòng tiếp theo mô tả các thư mục không kể thư mục gốc. Dòng thứ \(i\) trong số đó chứa hai số nguyên \(p_i,l_i\), cho biết thư mục \(i\) có tên dài \(l_i\) ký tự và nằm trực tiếp trong thư mục \(p_i\). Dữ liệu bảo đảm \(p_i<i\).

Cuối cùng là \(m\) dòng mô tả các tệp. Dòng thứ \(j\) trong số đó chứa hai số nguyên \(p_j,l_j\), cho biết tệp \(j\) có tên dài \(l_j\) ký tự và nằm trực tiếp trong thư mục \(p_j\).

Tên của mọi tệp và thư mục đều có độ dài dương. Các đường dẫn tuyệt đối ban đầu của chúng đều dài không quá \(k\) ký tự.

Dữ liệu ra

In \(m\) dòng, mỗi dòng ứng với một tệp. Dòng thứ \(j\) chứa YES nếu có thể thêm một liên kết tượng trưng có tên dài \(s\) ký tự để tạo ra một đường dẫn dài đúng \(k\) ký tự trỏ đến tệp \(j\); ngược lại, in NO.

Ràng buộc

• \(1\le n,m\le3000\).
• \(1\le k,s\le1\,000\,000\).
• Với thư mục \(i\), \(0\le p_i<i\) và \(l_i\ge1\).
• Với tệp \(j\), \(0\le p_j\le n\) và \(l_j\ge1\).
• Độ dài đường dẫn tuyệt đối ban đầu của mọi tệp và thư mục không vượt quá \(k\).

Phân nhóm

1. 33 điểm: \(n,m\le500\).
2. 33 điểm: \(n,m\le3000\); với mỗi tệp có đáp án YES, tồn tại cách thêm một liên kết tượng trưng và một đường dẫn dài đúng \(k\) đến tệp đó mà chỉ cần đi qua liên kết này nhiều nhất một lần.
3. 34 điểm: \(n,m\le3000\).

Ví dụ

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

YES
YES
YES
NO