게임

앨리스와 밥은 $N$개의 방과 이 방들을 연결하는 통로들로 이루어진 미로에서 게임을 하려고 한다.

미로의 방에는 $1, 2, \cdots, N$의 번호가 붙어 있다. 미로의 어떤 방들은 출구를 가지고 있는데, $i$ $(1 \le i \le N)$번 방에는 $A_i = 1$이면 출구가 있고, $A_i = 0$이면 없다.

미로를 연결하는 통로는 정확히 $M$쌍의 방 중 하나의 쌍을 연결한다. 같은 쌍의 방을 잇는 통로가 여러 개 존재할 수 있다.

구체적으로는, 각 $i$ $(1 \le i \le M)$에 대하여, $a_i$번 방과 $b_i$번 방을 잇는 서로 다른 통로가 $c_i$개 존재한다.

임의의 두 방 사이를 통로들을 통해 오갈 수 있음이 보장되지 않음에 유의하라.

앨리스와 밥은 총 $Q$번의 게임을 하려고 하는데, $j$ $(1 \le j \le Q)$번째 게임은 다음과 같이 진행된다.

• 앨리스가 미로의 $s_j$번 방으로 들어간다.

• 앨리스는 다음 규칙에 따라 인접한 방으로 이동할 수 있다.

  • 앨리스가 현재 $x$번 방에 있다 하자. 앨리스는 $x$번 방과 연결된 $k_j$개의 서로 다른 통로를 고른다. 이때 같은 방을 연결하는 여러 통로를 동시에 고를 수 있다. 만약 $x$번 방과 연결된 통로의 수가 $k_j$보다 작아 서로 다른 $k_j$개의 통로를 고르는 것이 불가능할 경우, 이동할 수 없다.
  • 앨리스가 선택을 마친 후 밥은 앨리스가 고른 $k_j$개의 통로 중 하나를 고른다.
  • 앨리스는 밥이 고른 통로가 잇는 반대쪽 방으로 이동한다.
• 앨리스가 위 규칙에 따라 다른 방으로 이동하는 것을 $0$번 이상 반복하여 출구가 있는 방에 도달하면 승리한다.

$s_j$번 방에 출구가 있는 경우, 게임이 시작할 때 앨리스가 있는 방에 출구가 있으므로 앨리스가 승리할 수 있음에 유의하라.

앨리스는 자신이 승리하기 위해서 최선을 다하며, 밥 역시 앨리스가 승리하지 못하게 하기 위해 최선을 다한다. 즉, 게임 중 밥이 어떤 선택을 하더라도 앨리스가 매 순간 적절한 선택을 하여 항상 출구가 있는 방에 도달할 수 있다면 앨리스가 승리하고, 그렇지 않으면 승리할 수 없다.

각 게임에 대해, 앨리스가 게임에서 승리할 수 있을지 아닐지를 판정하라.

• 주어지는 모든 수는 정수이다.
• $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점) 추가 제약 조건 없음.

첫 줄에 미로의 방의 수를 나타내는 정수 $N$, 통로 종류의 수를 나타내는 정수 $M$, 앨리스와 밥이 진행할 게임의 수를 나타내는 정수 $Q$가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 차례대로 주어진다.

그다음 $M$개의 줄에 걸쳐, 통로에 대한 정보가 주어진다. 이 중 $i$ $(1 \le i \le M)$번째 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 공백으로 구분되어 차례대로 주어진다. 이는 미로에 $a_i$번 방과 $b_i$번 방을 연결하는 $c_i$개의 통로가 있음을 의미한다.

그다음 $Q$개의 줄에 걸쳐, 앨리스와 밥이 진행할 $Q$번의 게임에 대한 정보가 주어진다. 이 중 $j$ $(1 \le j \le Q)$번째 줄에는 두 정수 $s_j$와 $k_j$가 공백으로 구분되어 차례대로 주어진다.

첫 줄부터 $Q$개의 줄에 걸쳐, 답을 출력한다. 이 중 $j$ $(1 \le j \le Q)$번째 줄에는 $j$번째 게임에 대하여 앨리스가 승리할 수 있다면 YES, 그렇지 않다면 NO를 출력해야 한다.