Alice và Bob chơi trong một mê cung gồm \(N\) phòng đánh số từ \(1\) đến \(N\). Phòng \(i\) có lối ra khi \(A_i=1\) và không có lối ra khi \(A_i=0\).

Mê cung có đúng \(M\) cặp phòng được nối. Với mỗi \(i\), có \(c_i\) hành lang khác nhau cùng nối hai phòng \(a_i\) và \(b_i\); vì vậy giữa cùng một cặp phòng có thể có nhiều hành lang song song. Mê cung không nhất thiết liên thông.

Họ chơi \(Q\) ván độc lập. Trong ván \(j\), Alice đi vào phòng \(s_j\) và có thể lặp lại thao tác sau:

1. Nếu đang ở phòng \(x\), Alice chọn đúng \(k_j\) hành lang khác nhau kề với \(x\). Cô có thể chọn nhiều hành lang song song dẫn đến cùng một phòng. Nếu bậc của \(x\) nhỏ hơn \(k_j\), Alice không thể di chuyển.
2. Sau khi Alice chọn, Bob chọn một trong \(k_j\) hành lang đó.
3. Alice đi qua hành lang Bob chọn đến phòng ở đầu kia.

Alice thắng ngay khi đến một phòng có lối ra, kể cả khi phòng xuất phát \(s_j\) đã có lối ra; cô được phép thực hiện \(0\) lần di chuyển. Alice cố gắng bảo đảm chiến thắng còn Bob cố ngăn cô thắng. Nói cách khác, Alice thắng nếu có một chiến lược thích nghi với các lựa chọn trước đó để cuối cùng luôn đến được một phòng có lối ra, bất kể Bob chọn thế nào.

Với mỗi ván, hãy xác định Alice có thể bảo đảm chiến thắng hay không.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,M,Q\).
• Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).
• \(M\) dòng tiếp theo: dòng \(i\) chứa \(a_i,b_i,c_i\), cho biết có \(c_i\) hành lang nối phòng \(a_i\) và \(b_i\).
• \(Q\) dòng tiếp theo: dòng \(j\) chứa \(s_j,k_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(j\) là YES nếu Alice có thể bảo đảm thắng ván \(j\), ngược lại là NO.

Ràng buộc

• \(1\le N\le200\,000\).
• \(0\le M\le400\,000\).
• \(1\le Q\le200\,000\).
• \(A_i\in\{0,1\}\) với mọi \(1\le i\le N\).
• \(1\le a_i<b_i\le N\) và \(1\le c_i\le10^9\) với mọi \(1\le i\le M\).
• Các cặp \((a_i,b_i)\) đôi một khác nhau.
• \(1\le s_j\le N\) và \(1\le k_j\le10^{18}\) với mọi \(1\le j\le Q\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(M=N-1\); với mọi \(1\le i\le M\), \(a_i=i\) và \(b_i=i+1\); chỉ phòng \(1\) có lối ra, tức \(A_1=1\) và \(A_2=A_3=\cdots=A_N=0\).
2. \(8\) điểm: \(M=N-1\); với mọi \(1\le i\le M\), \(a_i=1\) và \(b_i=i+1\).
3. \(7\) điểm: \(k_1=k_2=\cdots=k_Q=1\).
4. \(14\) điểm: \(k_1=k_2=\cdots=k_Q\).
5. \(15\) điểm: \(s_1=s_2=\cdots=s_Q\).
6. \(16\) điểm: \(N\le3\,000\), \(M\le3\,000\) và \(k_j\le3\,000\) với mọi \(1\le j\le Q\).
7. \(34\) điểm: không có ràng buộc thêm.

Ví dụ

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

YES
YES
YES
NO
NO

4 3 4
1 0 0 0
1 2 2
2 3 3
3 4 1
1 3
2 2
3 3
4 1

YES
YES
NO
YES

4 3 3
0 1 1 0
1 2 1
1 3 3
1 4 2
4 2
1 3
4 3

YES
YES
NO

2 0 2
1 0
1 1
2 1

YES
NO

Nguồn

KOI 2026 Round 2, bài Game. Tài liệu, dữ liệu chấm và mã nguồn mẫu của Korean Olympiad in Informatics, phát hành theo giấy phép CC BY-NC-SA 4.0.