E. Вкусные блюда
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти.

Есть $$$n$$$ поваров, пронумерованных $$$1, 2, \ldots, n$$$, которые готовят блюда для короля. Повар $$$i$$$ обладает мастерством $$$i$$$ и первоначально приготовил блюдо вкусности $$$a_i$$$, где $$$|a_i| \leq i$$$. У каждого повара есть список поваров, блюда которых он может копировать. Чтобы не допускать распространение плохих привычек, король гарантирует, что повар $$$i$$$ может копировать только у поваров с более высоким мастерством.

Повара работают над своими блюдами в течение нескольких дней. Каждый день работа над блюдом разбивается на два этапа.

  1. В начале каждого дня каждый повар может выбрать, поработать или нет над своим блюдом, тем самым умножая вкусность своего блюда на свое мастерство ($$$a_i := i \cdot a_i$$$).
  2. После того как все (кто хотел) поработали над своими блюдами, каждый повар начинает изучать работу других поваров. А именно, для каждого повара $$$j$$$ из списка повара $$$i$$$, повар $$$i$$$ может выбрать, скопировать ли блюдо повара $$$j$$$, тем самым прибавляя вкусность блюда $$$j$$$ к своему $$$i$$$-му блюду ($$$a_i := a_i + a_j$$$). Можно считать, что все копирования происходят одновременно. Иначе говоря, если повар $$$i$$$ хочет скопировать блюдо повара $$$j$$$, он скопирует вкусность блюдо повара $$$j$$$, полученную в конце этапа $$$1$$$.

Чтобы угодить королю, каждый повар стремятся максимизировать вкусность своего блюда.

Наконец, вам заданы $$$q$$$ запросов. Каждый запрос одно из двух видов:

  1. $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ — посчитайте сумму вкусностей $$$a_l, a_{l+1}, \ldots, a_{r}$$$ по окончании $$$k$$$-го дня. Так как данное значение может быть велико, выведите его по модулю $$$10^9 + 7$$$.
  2. $$$2$$$ $$$i$$$ $$$x$$$ — король дарит $$$x$$$ единиц вкусности блюду $$$i$$$-го повара перед началом $$$1$$$-го дня ($$$a_i := a_i + x$$$). Заметим, что королю нравятся вкусные блюда, а потому он дарит положительную вкусность ($$$x > 0$$$).

Обратите внимание, что запросы типа $$$1$$$ не зависят от других запросов. Точнее говоря, каждый запрос типа $$$1$$$ — это только возможный сценарий и он не меняет вкусности $$$a_i$$$ для запросов далее. При этом запросы типа $$$2$$$ накапливаются, но меняют только первоначальные значения $$$a_i$$$ блюд. В примечании представлены примеры запросов.

Входные данные

В первой строке задано одно целое число $$$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$$$ каждый день во время $$$2$$$-го этапа.

В следующей строке задано одно целое число $$$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$$$).

Гарантируется, что есть хотя бы один запрос первого вида.

Выходные данные

Для каждого запроса первого вида выведите одно число — ответ на этот запрос.

Пример
Входные данные
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
Выходные данные
57
71
316
278497818
Примечание

Ниже показаны множества поваров, у которых может копировать каждый из поваров в примере.

  • $$$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. $$$[1, 0, 0, 4, 20]$$$ (повара $$$4$$$ и $$$5$$$ работают над своими блюдами).
  2. $$$[25,0, 4, 24, 20]$$$ (повар $$$1$$$ копирует у поваров $$$4$$$ и $$$5$$$, повар $$$3$$$ копирует у повара $$$4$$$, повар $$$4$$$ копирует у повара $$$5$$$).

День 2

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

Можно показать, что на каждом описанном шаге все повара действовали оптимально.