Problem Description

Alice and Bob are going to play a game in a maze consisting of $N$ rooms and corridors connecting these rooms.

The rooms in the maze are numbered $1,2,\cdots,N$. Some rooms have exits: if room $i$ ($1 \le i \le N$) has an exit, then $A_i=1$; otherwise $A_i=0$.

The corridors in the maze connect exactly $M$ pairs of rooms. There may be multiple corridors connecting the same pair of rooms.

Specifically, for each $i$ ($1 \le i \le M$), there are $c_i$ distinct corridors connecting room $a_i$ and room $b_i$.

Note that it is not guaranteed that every pair of rooms is mutually reachable through corridors.

Alice and Bob will play a total of $Q$ games. Game $j$ ($1 \le j \le Q$) is played as follows:

• Alice enters room $s_j$ of the maze.
• Alice may move to an adjacent room according to the following rules.
  • Suppose Alice is currently in room $x$. Alice chooses $k_j$ distinct corridors that are connected to room $x$. Even if they connect the same pair of rooms, she may choose multiple different corridors. If there are fewer than $k_j$ corridors connected to room $x$, Alice loses the game and the game ends immediately.
  • After Alice makes her choice, Bob chooses one corridor from the $k_j$ corridors Alice selected.
  • Alice moves along the corridor chosen by Bob to the room at the other end.
• Alice repeats the process of moving to another room according to the rules above any number of times (including $0$ times). As soon as she reaches a room with an exit, she wins the game.

If room $s_j$ has an exit, then the room where Alice starts already has an exit, so Alice can win immediately.

Alice will do her best to win, and Bob will do his best to prevent Alice from winning. That is, if no matter how Bob chooses during the game, Alice can make appropriate choices at every step and eventually reach a room with an exit, then Alice wins; otherwise she cannot win.

For each game, determine whether Alice can win.

Input Format

The first line contains three integers $N$, $M$, and $Q$ separated by spaces, representing the number of rooms in the maze, the number of corridor types, and the number of games Alice and Bob will play.

The second line contains $N$ integers $A_1,A_2,\cdots,A_N$ separated by spaces.

The next $M$ lines describe the corridors. Line $i$ ($1 \le i \le M$) contains three integers $a_i,b_i,c_i$ separated by spaces, meaning there are $c_i$ corridors connecting room $a_i$ and room $b_i$.

The next $Q$ lines describe the $Q$ games Alice and Bob will play. Line $j$ ($1 \le j \le Q$) contains two integers $s_j$ and $k_j$ separated by spaces.

Output Format

Output $Q$ lines of answers starting from the first line. In line $j$ ($1 \le j \le Q$), output YES if Alice can win game $j$, otherwise output 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

Hint

Explanation of Sample 1

In this sample, the maze has $5$ rooms and $7$ corridors, and only room $3$ has an exit. Alice and Bob play $5$ games in total.

In the first game, Alice starts in room $2$, and she needs to choose $1$ corridor when moving. Alice first chooses a corridor leading to room $3$, and Bob can only choose that corridor. Therefore, Alice moves to room $3$, which has an exit, and wins the game.

In the second game, Alice starts in room $1$, and she needs to choose $2$ corridors when moving. Alice can win with the following strategy:

• First, choose one corridor leading to room $2$ and one corridor leading to room $3$, respectively.
  • If Bob chooses the corridor leading to room $3$, since room $3$ has an exit, Alice wins.
  • Suppose Bob chooses the corridor leading to room $2$. Then Alice chooses two corridors leading to room $3$. Bob must choose one of them, so Alice moves to room $3$ and wins.

Therefore, no matter how Bob chooses, Alice will eventually move to room $3$, which has an exit, and win.

In the third game, Alice starts in room $3$, and she needs to choose $3$ corridors when moving. Since room $3$ has an exit, Alice can win without making any move.

In the fourth game, Alice starts in room $4$, and she needs to choose $4$ corridors when moving. However, among the corridors connected to room $4$, there are $2$ corridors leading to room $1$ and $1$ corridor leading to room $3$, for a total of only $3$ corridors. Therefore, Alice cannot move and cannot win.

In the fifth game, Alice starts in room $5$, and she needs to choose $1$ corridor when moving. Room $5$ has no exit and is not connected by any corridor, so she cannot move to any other room. Thus, Alice cannot win.

Explanation of Sample 2

In the third game, Alice starts from room $3$, and she needs to choose $3$ corridors when moving. At this time, Bob can prevent Alice from winning with the following strategy:

• If among the corridors Alice chooses, there is at least one leading to room $4$, Bob chooses that corridor. Then Alice moves to room $4$. Since room $4$ is connected by only one corridor, Alice cannot continue moving, so she cannot win.
• If Alice does not choose any corridor leading to room $4$, then she can only choose three corridors leading to room $2$. Bob then chooses a corridor leading to room $2$, and Alice moves to room $2$.
• Among the corridors connected to room $2$, there are $2$ corridors leading to room $1$. In order to move, Alice must choose a corridor leading to room $3$. At this time, Bob also chooses the corridor leading to room $3$, making Alice return to room $3$ again.

Before Alice enters room $4$, Bob can keep repeating the strategy above. Therefore, no matter how many times Alice moves, she cannot reach the only room with an exit, room $1$, and thus cannot win.

Constraints

• All given values are integers.
• $1 \le N \le 200\,000$
• $0 \le M \le 400\,000$
• $1 \le Q \le 200\,000$
• For each integer $i$ ($1 \le i \le N$), $A_i$ is $0$ or $1$.
• For each integer $i$ ($1 \le i \le M$), $1 \le a_i<b_i \le N$.
• For any two distinct integers $i,j$ ($1 \le i,j \le M$), $a_i \ne a_j$ or $b_i \ne b_j$.
• For each integer $i$ ($1 \le i \le M$), $1 \le c_i \le 1\,000\,000\,000$.
• For each integer $j$ ($1 \le j \le Q$), $1 \le s_j \le N$.
• For each integer $j$ ($1 \le j \le Q$), $1 \le k_j \le 1\,000\,000\,000\,000\,000\,000$.

Subtasks

1. ($6$ points) $M=N-1$; for each integer $i$ ($1 \le i \le M$), $a_i=i$ and $b_i=i+1$. Only room $1$ has an exit, i.e. $A_1=1$ and $A_2=A_3=\cdots=A_N=0$.
2. ($8$ points) $M=N-1$; for each integer $i$ ($1 \le i \le M$), $a_i=1$ and $b_i=i+1$.
3. ($7$ points) $k_1=k_2=\cdots=k_Q=1$.
4. ($14$ points) $k_1=k_2=\cdots=k_Q$.
5. ($15$ points) $s_1=s_2=\cdots=s_Q$.
6. ($16$ points) $N \le 3\,000$, $M \le 3\,000$; for each integer $j$ ($1 \le j \le Q$), $k_j \le 3\,000$.
7. ($34$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5