시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 7 6 6 85.714%

문제

There is a wide mansion near JOI-kun’s house. The mansion has N rooms located in a row from east to west. The i-th room from the eastmost room is called the room i. For each i with 1 ≤ i ≤ N −1, the room i and the room i + 1 are connected by a corridor. We can pass corridors in both directions. We need a key to enter a corridor from a room. Each key has a number called the type. More than one keys can have the same type.

From the room i or the room i + 1, we need a key of type Ci to enter a corridor between them.

There are Bi keys in the room i. Their types are Ai, j (1 ≤ j ≤ Bi). If JOI-kun enters a room, he will pick up all the keys in that room. After that, he can use them to enter corridors.

JOI-kun can use keys as many times as he wants. Sometimes, he gets several keys of the same type. But, he has no special advantage to have several keys of the same type compared with the case where he has only one key of that type.

To deal with the situation where he gets lost in the mansion, JOI-kun plans to write a program which answers the following queries:

  • If JOI-kun comes into the room x without any keys, can he move to the room y?

Your task is to write a program which answers the above queries, instead of JOI-kun.

Given information of the mansion and the queries, write a program which determines, for each query, whether he can move from a room to another room assuming he is now in the mansion without any keys.

입력

Read the following data from the standard input.

  • The first line of input contains an integer N, the number of rooms in the mansion.
  • The second line of input contains N − 1 space separated integers C1, C2, . . . ,CN−1. This means we need a key of type Ci to enter a corridor connecting the room i and the room i + 1.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains a positive integer Bi, and Bi space separated integers Ai,1, Ai,2, . . . , Ai,Bi. This means there are Bi keys in the room i, and their types are Ai,j (1 ≤ j ≤ Bi).
  • The following line contains an integer Q, the number of queries.
  • The k-th line (1 ≤ k ≤ Q) of the following Q lines contains two space separated integers Xk, Yk. This means the k-th query asks whether JOI-kun can move from the room Xk to the room Yk assuming he is now in the room Xk without any keys.

출력

Write Q lines to the standard output. The k-th line (1 ≤ k ≤ Q) of the Q lines contains YES if he can move from the room Xk to the room Yk assuming he is now in the room Xk without any keys. Otherwise, it contains NO.

제한

  • 2 ≤ N ≤ 500 000.
  • 1 ≤ Q ≤ 500 000.
  • 1 ≤ B1 + B2 + · · · + BN ≤ 500 000.
  • 1 ≤ Bi ≤ N (1 ≤ i ≤ N).
  • 1 ≤ Ci ≤ N (1 ≤ i ≤ N − 1).
  • 1 ≤ Ai,j ≤ N (1 ≤ i ≤ N, 1 ≤ j ≤ Bi).
  • The Bi integers Ai,1, . . . , Ai,Bi are different from each other (1 ≤ i ≤ N).
  • 1 ≤ Xk ≤ N (1 ≤ k ≤ Q).
  • 1 ≤ Yk ≤ N (1 ≤ k ≤ Q).
  • Xk ≠ Yk (1 ≤ k ≤ Q).

예제 입력 1

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

예제 출력 1

YES
NO
NO
YES
  • In the first query, if JOI-kun visits the rooms 2, 1, 2, 3, 4 in this order, he gets to the room 4.
  • In the second query, he can visit the rooms 3, 4 only. Since he can get keys of type 1, 3 only, he can not get to the room 2.
  • In the third query, he can not get a key of type 4 from the room 5 to the room 4. Hence he can not get to the room 5.
  • In the fourth query, if he visits the rooms 5, 4, 3 in this order, he gets to the room 3.

예제 입력 2

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

예제 출력 2

NO
YES
NO
YES

예제 입력 3

7
6 3 4 1 2 5
1 1
1 5
1 1
1 1
2 2 3
1 4
1 6
3
4 1
5 3
4 7

예제 출력 3

YES
NO
YES