Tasty Dishes

ID: 2066

Type: RemoteJudge

10000ms

64MiB

Tried: 0

Accepted: 0

Difficulty: 10

Uploaded By:

Hydro

Tags>

math

matrices

*3500

Description

Note 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.

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.

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

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 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.

Sample Input 1

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

Sample Output 1

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.

#P1540E. Tasty Dishes

Description

Input

Output

Note

Status

Development

Support

#P1540E. Tasty Dishes

Tasty Dishes

Description

Input

Output

Sample Input 1

Sample Output 1

Note

Status

Development

Support

Don't have an account?

SIGN IN