406024: GYM102219 G Timeout

Abu is working on a web application's backend. Like any other server, his server have multiple endpoints for many different purpose. Each of his endpoint is described as multiple tasks, where each task can depend on other tasks. Abu likes to describe his endpoints like this because it is easy and safe to parallelize. For example, let say his endpoint consist of five task, $$$A, B, C, D$$$ and $$$E$$$. $$$B$$$ depends on $$$A$$$. $$$D$$$ depends on $$$C$$$ and $$$B$$$. $$$E$$$ depends on $$$D$$$. Because $$$A$$$ and $$$C$$$ does not depends on each other they can run at the same time. And when $$$A$$$ is completed, $$$B$$$ can start running regardless if $$$C$$$ have been completed or not. When both $$$B$$$ and $$$C$$$ have completed, regardless of which one finish first, $$$D$$$ can start running.

Now, Abu's server is getting more and more traffic lately and it is important for him to know the runtime of some of his endpoint. He knows you are good at this sort of things, so he ask for your help. Given a description of his system, which consist of multiple endpoints, and a list of query, determine the runtime of the queried endpoint. Each endpoint is described as multiple task which may depends on zero or more other task from the same endpoint. A task can either be a calculation whose runtime will be given, or another endpoint call whose runtime, is the runtime of the specified endpoint, plus a fixed network latency of $$$1$$$.

You are to assume an endpoint will ran all its task as optimally as possible with maximum parallelization. There will not be a cycle in the chain of endpoint calls. In another word, an endpoint $$$A$$$ will never call an endpoint $$$B$$$ which will call endpoint $$$A$$$, or call other endpoint which eventually goes back to $$$A$$$.

The input starts with an integer $$$n, m$$$ $$$(1 ≤ m ≤ n ≤ 2×10^{4} )$$$ which is the number of endpoint and number of query. $$$n$$$ description of endpoint follows.

Each endpoint description starts with an integer $$$k$$$ $$$(1 ≤ k ≤ 10^{2} )$$$ which is the number of task for that endpoint. Each task is numbered from $$$1$$$ to $$$k$$$ and described in order as follows.

Each task description consist of two line. The first line describe the task dependency. The first line starts with an integer $$$l$$$ $$$(0 ≤ l ≤ k)$$$ which is the number of dependency. The next $$$l$$$ integer is the task that the current task depends on. The second line describe the task itself. It consist of two integer that starts with $$$o$$$ which is the type of task. If it is $$$0$$$ it is a calculation, and the second integer $$$r$$$ $$$(0 ≤ r ≤ 10^{3} )$$$ is the runtime of the task. If it is a $$$1$$$ it is an endpoint call and the second integer $$$e$$$ $$$(1 ≤ e ≤ n)$$$ is the number for the endpoint.

The next $$$m$$$ line each consist of a single integer $$$q_{i}$$$ $$$(1 ≤ q_{i} ≤ n)$$$ which is the number for the endpoint that is being queried.

For each $$$q_{i}$$$, print a line containing a single integer, which is the runtime for that particular endpoint. As the runtime can be very high, modulus each $$$q_{i}$$$ by $$$10^{9} + 7$$$.

3 2
5
0
0 100
1 1
1 2
1 1
1 3
0
0 10
3 2 3 4
0 1
1
0
0 1000
2
0
0 100
1 1
1 2
1
2

1203
1000

Large input file. Do not use slow IO.