Codeforces Round 728 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

matrices

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Tasty Dishes

time limit per test

10 secondsmemory limit per test

64 megabytesinput

standard inputoutput

standard outputNote that the memory limit is unusual.

There are $$$n$$$ chefs numbered $$$1, 2, \ldots, n$$$ that must prepare dishes for a king. Chef $$$i$$$ has skill $$$i$$$ and initially has a dish of tastiness $$$a_i$$$ where $$$|a_i| \leq i$$$. Each chef has a list of other chefs that he is allowed to copy from. To stop chefs from learning bad habits, the king makes sure that chef $$$i$$$ can only copy from chefs of larger skill.

There are a sequence of days that pass during which the chefs can work on their dish. During each day, there are two stages during which a chef can change the tastiness of their dish.

- At the beginning of each day, each chef can choose to work (or not work) on their own dish, thereby multiplying the tastiness of their dish of their skill ($$$a_i := i \cdot a_i$$$) (or doing nothing).
- After all chefs (who wanted) worked on their own dishes, each start observing the other chefs. In particular, for each chef $$$j$$$ on chef $$$i$$$'s list, chef $$$i$$$ can choose to copy (or not copy) $$$j$$$'s dish, thereby adding the tastiness of the $$$j$$$'s dish to $$$i$$$'s dish ($$$a_i := a_i + a_j$$$) (or doing nothing). It can be assumed that all copying occurs simultaneously. Namely, if chef $$$i$$$ chooses to copy from chef $$$j$$$ he will copy the tastiness of chef $$$j$$$'s dish at the end of stage $$$1$$$.

All chefs work to maximize the tastiness of their own dish in order to please the king.

Finally, you are given $$$q$$$ queries. Each query is one of two types.

- $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ — find the sum of tastiness $$$a_l, a_{l+1}, \ldots, a_{r}$$$ after the $$$k$$$-th day. Because this value can be large, find it modulo $$$10^9 + 7$$$.
- $$$2$$$ $$$i$$$ $$$x$$$ — the king adds $$$x$$$ tastiness to the $$$i$$$-th chef's dish before the $$$1$$$-st day begins ($$$a_i := a_i + x$$$). Note that, because the king wants to see tastier dishes, he only adds positive tastiness ($$$x > 0$$$).

Note that queries of type $$$1$$$ are independent of each all other queries. Specifically, each query of type $$$1$$$ is a scenario and does not change the initial tastiness $$$a_i$$$ of any dish for future queries. Note that queries of type $$$2$$$ are cumulative and only change the initial tastiness $$$a_i$$$ of a dish. See notes for an example of queries.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of chefs.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-i \le a_i \le i$$$).

The next $$$n$$$ lines each begin with a integer $$$c_i$$$ ($$$0 \le c_i < n$$$), denoting the number of chefs the $$$i$$$-th chef can copy from. This number is followed by $$$c_i$$$ distinct integers $$$d$$$ ($$$i < d \le n$$$), signifying that chef $$$i$$$ is allowed to copy from chef $$$d$$$ during stage $$$2$$$ of each day.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains a query of one of two types:

- $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 1000$$$);
- $$$2$$$ $$$i$$$ $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 1000$$$).

It is guaranteed that there is at least one query of the first type.

Output

For each query of the first type, print a single integer — the answer to the query.

Example

Input

5 1 0 -2 -2 4 4 2 3 4 5 1 3 1 4 1 5 0 7 1 1 1 5 2 4 3 1 1 1 5 2 3 2 1 2 2 4 2 5 1 1 981 4 5

Output

57 71 316 278497818

Note

Below is the set of chefs that each chef is allowed to copy from:

- $$$1$$$: $$$\{2, 3, 4, 5\}$$$
- $$$2$$$: $$$\{3\}$$$
- $$$3$$$: $$$\{4\}$$$
- $$$4$$$: $$$\{5\}$$$
- $$$5$$$: $$$\emptyset$$$ (no other chefs)

Following is a description of the sample.

For the first query of type $$$1$$$, the initial tastiness values are $$$[1, 0, -2, -2, 4]$$$.

The final result of the first day is shown below:

- $$$[1, 0, -2, -2, 20]$$$ (chef $$$5$$$ works on his dish).
- $$$[21, 0, -2, 18, 20]$$$ (chef $$$1$$$ and chef $$$4$$$ copy from chef $$$5$$$).

So, the answer for the $$$1$$$-st query is $$$21 + 0 - 2 + 18 + 20 = 57$$$.

For the $$$5$$$-th query ($$$3$$$-rd of type $$$1$$$). The initial tastiness values are now $$$[1, 0, 0, 1, 4]$$$.

Day 1

- $$$[1, 0, 0, 4, 20]$$$ (chefs $$$4$$$ and $$$5$$$ work on their dishes).
- $$$[25,0, 4, 24, 20]$$$ (chef $$$1$$$ copies from chefs $$$4$$$ and $$$5$$$, chef $$$3$$$ copies from chef $$$4$$$, chef $$$4$$$ copies from chef $$$5$$$).

Day 2

- $$$[25, 0, 12, 96, 100]$$$ (all chefs but chef $$$2$$$ work on their dish).
- $$$[233, 12, 108, 196, 100]$$$ (chef $$$1$$$ copies from chefs $$$3$$$, $$$4$$$ and $$$5$$$, chef $$$2$$$ from $$$3$$$, chef $$$3$$$ from $$$4$$$, chef $$$4$$$ from chef $$$5$$$).
So, the answer for the $$$5$$$-th query is $$$12+108+196=316$$$.

It can be shown that, in each step we described, all chefs moved optimally.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2023 08:20:43 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|