题目描述

Alice 和 Bob 要在一座由 $N$ 个房间以及连接这些房间的通道组成的迷宫中进行游戏。

迷宫中的房间编号为 $1,2,\cdots,N$。其中一些房间有出口：若第 $i$（$1 \le i \le N$）个房间有出口，则 $A_i=1$；否则 $A_i=0$。

迷宫中的通道恰好连接 $M$ 对房间。连接同一对房间的通道可以有多条。

具体而言，对于每个 $i$（$1 \le i \le M$），有 $c_i$ 条互不相同的通道连接第 $a_i$ 个房间与第 $b_i$ 个房间。

请注意，不保证任意两个房间之间都能通过通道相互到达。

Alice 和 Bob 总共要进行 $Q$ 局游戏。第 $j$（$1 \le j \le Q$）局游戏按如下方式进行：

• Alice 进入迷宫的第 $s_j$ 个房间。
• Alice 可以按照以下规则移动到相邻房间。
  • 假设 Alice 当前位于第 $x$ 个房间。Alice 选择与第 $x$ 个房间相连的 $k_j$ 条互不相同的通道。即使连接同一对房间，也可以选择多条不同的通道。如果与第 $x$ 个房间相连的通道少于 $k_j$ 条，Alice 将输掉游戏，且游戏立即结束。
  • Alice 做出选择后，Bob 从 Alice 所选的 $k_j$ 条通道中选择一条。
  • Alice 沿 Bob 所选的通道移动到另一端的房间。
• Alice 将按照上述规则移动到另一个房间的过程重复任意多次（包括 $0$ 次）。一旦到达有出口的房间，她就赢得游戏。

如果第 $s_j$ 个房间有出口，那么游戏开始时 Alice 所在的房间就有出口，因此 Alice 可以直接获胜。

Alice 会尽最大努力获胜，Bob 也会尽最大努力阻止 Alice 获胜。也就是说，如果无论 Bob 在游戏中如何选择，Alice 都能在每一步作出恰当的选择并最终到达有出口的房间，则 Alice 获胜；否则她无法获胜。

对于每局游戏，请判断 Alice 是否能够获胜。

输入格式

第一行依次给出以空格分隔的三个整数 $N$、$M$、$Q$，分别表示迷宫的房间数、通道种类数以及 Alice 和 Bob 将进行的游戏局数。

第二行依次给出 $N$ 个以空格分隔的整数 $A_1,A_2,\cdots,A_N$。

接下来的 $M$ 行给出通道信息。其中第 $i$（$1 \le i \le M$）行依次给出三个以空格分隔的整数 $a_i,b_i,c_i$，表示迷宫中有 $c_i$ 条通道连接第 $a_i$ 个房间和第 $b_i$ 个房间。

再接下来的 $Q$ 行给出 Alice 和 Bob 将进行的 $Q$ 局游戏的信息。其中第 $j$（$1 \le j \le Q$）行依次给出两个以空格分隔的整数 $s_j$ 和 $k_j$。

输出格式

从第一行开始依次输出 $Q$ 行答案。第 $j$（$1 \le j \le Q$）行中，如果 Alice 能在第 $j$ 局游戏中获胜，则输出 YES；否则输出 NO。

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

提示

样例 1 解释

在此样例中，迷宫共有 $5$ 个房间和 $7$ 条通道，且只有第 $3$ 个房间有出口。Alice 和 Bob 共进行 $5$ 局游戏。

在第一局游戏中，Alice 最初位于第 $2$ 个房间，移动时需要选择 $1$ 条通道。Alice 首先选择一条通向第 $3$ 个房间的通道，Bob 只能选择同一条通道。因此 Alice 移动到有出口的第 $3$ 个房间，并赢得游戏。

在第二局游戏中，Alice 最初位于第 $1$ 个房间，移动时需要选择 $2$ 条通道。Alice 可以按以下策略获胜：

• 首先分别选择一条通向第 $2$ 个房间和一条通向第 $3$ 个房间的通道。
  • 如果 Bob 选择通向第 $3$ 个房间的通道，因为第 $3$ 个房间有出口，所以 Alice 获胜。
  • 假设 Bob 选择了通向第 $2$ 个房间的通道。此时 Alice 选择两条通向第 $3$ 个房间的通道，Bob 必须从中选择一条，因此 Alice 移动到第 $3$ 个房间并赢得游戏。

因此，无论 Bob 如何选择，Alice 最终都会移动到有出口的第 $3$ 个房间并获胜。

在第三局游戏中，Alice 最初位于第 $3$ 个房间，移动时需要选择 $3$ 条通道。由于第 $3$ 个房间有出口，Alice 无需进行任何移动即可获胜。

在第四局游戏中，Alice 最初位于第 $4$ 个房间，移动时需要选择 $4$ 条通道。然而，与第 $4$ 个房间相连的通道中，通向第 $1$ 个房间的有 $2$ 条，通向第 $3$ 个房间的有 $1$ 条，总共只有 $3$ 条。因此 Alice 无法移动，也无法获胜。

在第五局游戏中，Alice 最初位于第 $5$ 个房间，移动时需要选择 $1$ 条通道。第 $5$ 个房间没有出口，也没有连接任何通道，因此无法移动到其他房间。于是 Alice 无法获胜。

样例 2 解释

在第三局游戏中，Alice 从第 $3$ 个房间开始，移动时需要选择 $3$ 条通道。此时，Bob 可以按以下策略阻止 Alice 获胜：

• 如果 Alice 选择的通道中至少有一条通向第 $4$ 个房间，Bob 就选择这条通道。这样 Alice 会移动到第 $4$ 个房间。由于第 $4$ 个房间只连接一条通道，Alice 无法继续移动，因此无法获胜。
• 如果 Alice 没有选择通向第 $4$ 个房间的通道，那么她只能选择三条通向第 $2$ 个房间的通道。此时 Bob 选择一条通向第 $2$ 个房间的通道，Alice 移动到第 $2$ 个房间。
• 与第 $2$ 个房间相连的通道中，有 $2$ 条通向第 $1$ 个房间。为了移动，Alice 必须选择一条通向第 $3$ 个房间的通道。此时 Bob 也选择通向第 $3$ 个房间的通道，使 Alice 再次回到第 $3$ 个房间。

在 Alice 进入第 $4$ 个房间之前，Bob 可以一直重复上述策略。因此无论 Alice 移动多少次，她都无法到达唯一有出口的第 $1$ 个房间，因而无法获胜。

限制条件

• 给出的所有数均为整数。
• $1 \le N \le 200\,000$
• $0 \le M \le 400\,000$
• $1 \le Q \le 200\,000$
• 对于每个整数 $i$（$1 \le i \le N$），$A_i$ 为 $0$ 或 $1$。
• 对于每个整数 $i$（$1 \le i \le M$），$1 \le a_i<b_i \le N$。
• 对于任意两个互不相同的整数 $i,j$（$1 \le i,j \le M$），$a_i \ne a_j$ 或 $b_i \ne b_j$。
• 对于每个整数 $i$（$1 \le i \le M$），$1 \le c_i \le 1\,000\,000\,000$。
• 对于每个整数 $j$（$1 \le j \le Q$），$1 \le s_j \le N$。
• 对于每个整数 $j$（$1 \le j \le Q$），$1 \le k_j \le 1\,000\,000\,000\,000\,000\,000$。

子任务

1. （$6$ 分）$M=N-1$；对于每个整数 $i$（$1 \le i \le M$），$a_i=i$ 且 $b_i=i+1$。仅第 $1$ 个房间有出口，即 $A_1=1$ 且 $A_2=A_3=\cdots=A_N=0$。
2. （$8$ 分）$M=N-1$；对于每个整数 $i$（$1 \le i \le M$），$a_i=1$ 且 $b_i=i+1$。
3. （$7$ 分）$k_1=k_2=\cdots=k_Q=1$。
4. （$14$ 分）$k_1=k_2=\cdots=k_Q$。
5. （$15$ 分）$s_1=s_2=\cdots=s_Q$。
6. （$16$ 分）$N \le 3\,000$，$M \le 3\,000$；对于每个整数 $j$（$1 \le j \le Q$），$k_j \le 3\,000$。
7. （$34$ 分）没有额外限制。

翻译由 ChatGPT-5.6 完成