CF1540E.Tasty Dishes

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.

1. 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).
2. 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. $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. $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 \gt 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.

注意：本题的内存限制较为特殊。

有 $n$ 位厨师，编号为 $1, 2, \ldots, n$，他们需为国王准备菜肴。厨师 $i$ 的技能值为 $i$，初始时其菜肴的美味度为 $a_i$，满足 $|a_i| \leq i$。每位厨师均拥有一张允许其模仿的其他厨师列表。为防止厨师沾染不良习惯，国王规定：厨师 $i$ 只能向技能值严格更大的厨师学习（即只能从技能值 $> i$ 的厨师处模仿）。

在若干天中，厨师们可不断改进自己的菜肴。每天分为两个阶段，厨师可在其中改变自己菜肴的美味度：

1. 每天开始时，每位厨师可选择是否对自己的菜肴进行加工（也可选择不操作），若加工，则将其菜肴美味度乘以其自身技能值（即执行 $a_i := i \cdot a_i$）；
2. 所有厨师完成第 1 阶段操作后，每位厨师开始观察列表中的其他厨师。具体而言，对厨师 $i$ 列表中的每位厨师 $j$，厨师 $i$ 可选择是否模仿 $j$ 的菜肴（也可选择不模仿），若模仿，则将其菜肴美味度加上厨师 $j$ 当前的美味度（即执行 $a_i := a_i + a_j$）；所有模仿操作是同时进行的，即厨师 $i$ 若选择模仿厨师 $j$，则所加的值为厨师 $j$ 在第 1 阶段结束后的美味度。

所有厨师的目标均为最大化自己菜肴的美味度，以取悦国王。

最后，你将收到 $q$ 个查询，每个查询为以下两种类型之一：

1. 1 k l r —— 求第 $k$ 天结束后，美味度之和 $a_l + a_{l+1} + \cdots + a_r$ 的值；由于该值可能极大，请对 $10^9 + 7$ 取模输出。
2. 2 i x —— 国王在第 $1$ 天开始前，向第 $i$ 位厨师的菜肴额外添加 $x$ 美味度（即执行 $a_i := a_i + x$）。注意：因国王希望看到更美味的菜肴，故只添加正数美味度（即 $x > 0$）。

注意：类型 $1$ 的查询彼此相互独立。具体而言，每个类型 $1$ 的查询仅对应一个独立场景，不会影响后续查询中任何菜肴的初始美味度 $a_i$。而类型 $2$ 的查询是累加的，仅修改某菜肴的初始美味度 $a_i$。关于查询的示例，请参见题目末尾的“说明”部分。

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 \lt n$), denoting the number of chefs the $i$-th chef can copy from. This number is followed by $c_i$ distinct integers $d$ ($i \lt 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.

第一行包含一个整数 $n$（$1 \le n \le 300$）—— 厨师的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-i \le a_i \le i$）。

接下来的 $n$ 行，每行以一个整数 $c_i$（$0 \le c_i < n$）开头，表示第 $i$ 位厨师在每天第二阶段中可以模仿的厨师数量。该整数后跟 $c_i$ 个互不相同的整数 $d$（$i < d \le n$），表示第 $i$ 位厨师在每天第二阶段中允许模仿第 $d$ 位厨师。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）—— 查询的数量。

接下来的 $q$ 行中，每行包含以下两种类型之一的查询：

• $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$）。

保证至少存在一个第一类查询。

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

对于每个第一类查询，输出一个整数——该查询的答案。

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. $[1, 0, -2, -2, 20]$ (chef $5$ works on his dish).
2. $[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. $[1, 0, 0, 4, 20]$ (chefs $4$ and $5$ work on their dishes).
2. $[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

1. $[25, 0, 12, 96, 100]$ (all chefs but chef $2$ work on their dish).

2. $[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.

以下是每位厨师被允许抄袭的厨师集合：

• $1$: ${2, 3, 4, 5}$
• $2$: ${3}$
• $3$: ${4}$
• $4$: ${5}$
• $5$: $\emptyset$（无其他厨师）

以下是样例说明。

对于第一个类型为 $1$ 的查询，初始美味度值为 $[1, 0, -2, -2, 4]$。

第一天的最终结果如下所示：

1. $[1, 0, -2, -2, 20]$（厨师 $5$ 对其菜品进行操作）。
2. $[21, 0, -2, 18, 20]$（厨师 $1$ 和厨师 $4$ 向厨师 $5$ 抄袭）。

因此，第 $1$ 个查询的答案为 $21 + 0 - 2 + 18 + 20 = 57$。

对于第 $5$ 个查询（即第 $3$ 个类型为 $1$ 的查询），当前初始美味度值为 $[1, 0, 0, 1, 4]$。

第一天：

1. $[1, 0, 0, 4, 20]$（厨师 $4$ 和厨师 $5$ 对其菜品进行操作）。
2. $[25, 0, 4, 24, 20]$（厨师 $1$ 向厨师 $4$ 和厨师 $5$ 抄袭，厨师 $3$ 向厨师 $4$ 抄袭，厨师 $4$ 向厨师 $5$ 抄袭）。

第二天：

1. $[25, 0, 12, 96, 100]$（除厨师 $2$ 外，其余所有厨师均对其菜品进行操作）。
2. $[233, 12, 108, 196, 100]$（厨师 $1$ 向厨师 $3$、$4$ 和 $5$ 抄袭，厨师 $2$ 向厨师 $3$ 抄袭，厨师 $3$ 向厨师 $4$ 抄袭，厨师 $4$ 向厨师 $5$ 抄袭）。

因此，第 $5$ 个查询的答案为 $12+108+196=316$。

可以证明，在我们所描述的每一步中，所有厨师均采取了最优行动。