L. List of Orders
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

NTU Factory recently received $$$N$$$ orders, each containing the following information:

  1. The final item to be produced.
  2. The earliest start time. For example, the required materials for the final item may arrive at a certain time.
  3. The expected deadline $$$d_i$$$.

To complete each final item, the factory needs to go through multiple works. These works cannot be parallelized; that is, the $$$(i + 1)$$$-th work can only start after the $$$i$$$-th work is done. More precisely, each order is divided into $$$k_i$$$ works $$$w_{i, 1}, w_{i, 2}, \ldots, w_{i, k_i}$$$, representing the $$$k_i$$$ works within the order. For each work $$$a$$$, there is an item $$$z_a$$$ required to be produced. Once all these $$$k_i$$$ works are done, the final item is then magically produced.

To maintain the responsiblility of each factory labor, there are certain constraints when multiple works aim to produce the same item:

  1. These works cannot be performed simultaneously; one must be completed before the other starts.
  2. To determine which work should be done earlier, the labors should follow the following rule. Recall that each work belongs to an order, right? A work belonging to an order with earlier deadline should be done first. That is, if we focus on all the works producing a specific item $$$z$$$ and sort these works in chronological order of their completion time, it should have also been sorted by the deadlines of their belonging order.

To complete the numerous works, the factory needs $$$M$$$ resources. For each resource, the factory must assign a production sequence, specifying the order of works in which each resource should process. These assigned production sequences form a production plan. Once the production plan is determined, each resource starts processing works according to its assigned sequence. However, if a resource finds that the next work it needs to process depends on other works that have not been completed, the resource will pause until all dependencies are resolved before continuing.

Currently, NTU Factory's production plan is manually determined, but the existing method, though free from sequence conflicts, is highly inefficient, leading to many delayed orders. To improve production efficiency, the NTU Factory owner asks the engineers to use programming techniques to optimize the production plan.

The engineer has come up with the following method: Define a state as the production sequence for each resource. The initial state can be obtained from the current production plan. After obtaining the initial state, the following improvements are repeatedly carried out:

  • Step 1. Select a continuous segment of works on one resource.
  • Step 2. Attempt to insert this continuous segment of works into the production sequence of a certain resource (which can be the same resource).
  • Step 3. Temporarily store the new state as a test production plan and evaluate whether to accept this new state based on production efficiency, the number of delayed orders, and other evaluation metrics. The new state will not be adopted if it performs poorly.

The current issue faced by the engineer is that Step 2 may lead to conflicts in the work sequence. For example, the production plan may cause two resources to wait for each other's works to be completed, resulting in both resources pausing and not processing any works.

Therefore, the engineer entrusts you with the task of implementing a procedure that can input the current production plan, select a continuous segment of works in Step 1, and then repeatedly answer whether conflicts will occur in the work sequence after attempting to insert this segment of works into a specified new position in Step 2.

Input

The input is divided into three parts: information of the orders, production plan, and queries, each separated by an empty line for easy identification.

Information of the Orders

The first line contains two positive integers $$$N$$$ and $$$W$$$, representing the number of orders and the number of works.

The following $$$N$$$ lines represent the $$$N$$$ orders. The $$$i$$$-th line begins with two positive integers $$$d_i$$$ and $$$k_i$$$, indicating the deadline and the number of works for the $$$i$$$-th order. Following that are $$$k_i$$$ positive integers, where the $$$j$$$-th integer $$$w_{i, j}$$$ represents the index of the $$$j$$$-th work in the order, representing the execution order of the works required for this order.

Next is one line with $$$W$$$ positive integers $$$z_1, z_2, \ldots, z_W$$$, where $$$z_i$$$ represents the item number that the $$$i$$$-th work is intended to produce.

  • $$$1 \leq N, W \leq 10^5$$$
  • $$$1 \leq d_i \leq 10^9$$$
  • All $$$d_i$$$ are distinct.
  • $$$\sum^{N}_{i=1} k_i = W$$$
  • $$$1 \leq w_{i, j} \leq W$$$
  • Each work will appear once in exactly one order.
  • Works within the same order will not produce the same item.
  • $$$1 \leq z_i \leq 10^9$$$

Production Plan

The first line contains a positive integer $$$M$$$, representing the number of resources.

The following $$$M$$$ lines represent the initial production plan. The $$$i$$$-th line begins with a positive integer $$$t_i$$$, indicating the number of works assigned to resource $$$i$$$. Following that are $$$t_i$$$ positive integers, where the $$$j$$$-th integer $$$x_{i, j}$$$ represents the index of the $$$j$$$-th work in the order of execution for resource $$$i$$$.

  • $$$1 \leq M \leq 10^5$$$
  • $$$\sum^{M}_{i=1} t_i = W$$$
  • $$$1 \leq x_{i, j} \leq W$$$
  • Each work will appear once in exactly one resource.
  • It is guaranteed that the initial production plan does not have any conflicts.

Queries

The first line contains four positive integers $$$Q, u, l, r$$$, representing the number of queries, the resource number specified in Step 1, and the continuous segment of works selected in Step 1, which is the interval $$$x_{u, l}, x_{u, l+1}, \ldots, x_{u, r}$$$.

The following $$$Q$$$ lines each contain two integers $$$v_i, p_i$$$, representing the selection of inserting this segment of works into resource $$$v_i$$$ after the $$$p_i$$$-th work in the production sequence. Specifically, if $$$p_i = 0$$$, it means inserting this segment of works at the beginning of the production sequence of resource $$$v_i$$$, that is, before the first work $$$x_{v_i, 1}$$$.

  • $$$1 \leq Q \leq 10^5$$$
  • $$$1 \leq u \leq M$$$
  • $$$1 \leq l \leq r \leq t_u$$$
  • $$$1 \leq v_i \leq M$$$
  • $$$0 \leq p_i \leq t_{v_i}$$$
  • In particular, if $$$u = v_i$$$, then $$$p_i \lt l$$$ or $$$p_i \gt r$$$.
Output

For each query, output one line with Yes if inserting this way will not cause conflicts in the work sequence, or No otherwise.

Example
Input
3 10
10 3 1 2 3
20 4 4 5 6 7
30 3 8 9 10
42 49 114 514 42 49 114 49 42 2023

4
2 1 8
3 2 5 6
2 3 4
3 7 9 10

5 2 2 3
1 1
2 0
3 2
3 1
4 3
Output
Yes
No
Yes
No
No