시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

There are $N$ power generators and $M$ appliances. The $i$th generator produces a power of $A_i$. The $j$th appliance is connected to a set of generator $S_j$ and gets its energy from them. Let $C_j$ be the number of generators in $S_j$.

The energy obtained by each appliance can be calculated with the following formula.

$$\displaystyle\sum_{1 \le a \le b \le C_j}{A_{S_{j}[a]} \cdot A_{S_{j}[b]}}$$

For example, let’s say an appliance gets its energy from 4 generators and each of them produces $10$, $5$, $20$, and $5$ of power, respectively. The energy obtained by this appliance is $10\cdot 5+10\cdot 20+10\cdot 5+5\cdot 20+5\cdot 5+20\cdot 5 = 50 + 200 + 50 + 100 + 25 + 100 = 525$.

For the next $Q$ days, you will perform one of these two operations.

  1. Change the power produced by the $i$th generator to $X$.
  2. Report the energy obtained by the $j$th appliance.

For each operation of the second type, output the energy obtained by the $j$th appliance.

입력

Input begins with a line containing two integers: $N$ $M$ ($1 \le N, M \le 100~000$) representing the number of power generators and the number of appliances, respectively. The next line contains $N$ integers: $A_i$ ($1 \le A_i \le 10~000$) representing the power produced by the generators initially. The next $M$ lines each begins with an integer $C_j$ ($1 \le C_j \le N$) representing the number of generators that are connected to the $j$th appliance, followed by $C_j$ integers: $S_j[k]$ ($1 \le S_j[k] \le N$) representing the connected generators. For all $j$, the generators in $S_j$ are guaranteed to be unique. The sum of all $C_j$ is not more than $200~000$.

The next line contains an integer: $Q$ ($1 \le Q \le 100~000$) representing the number of days. The next $Q$ lines each contains one of the following input format representing the operation you should perform.

  • 1 $i$ $X$ ($1 \le i \le N$; $1 \le X \le 10~000$)
    Change the power produced by the $i$th generator to $X$.
  • 2 $j$ ($1 \le j \le M$)
    Output the energy obtained by the $j$th appliance.

There will be at least one operation of the second type.

출력

For each operation of the second type in the same order as input, output in a line an integer representing the energy obtained by the $j$th appliance.

예제 입력 1

3 2
1 2 3
3 1 2 3
2 1 3
5
2 1
2 2
1 2 10
2 1
2 2

예제 출력 1

11
3
43
3

There are $3$ generators and initially, each of them produces $1$, $2$, and $3$ of power, respectively.

  • 2 1
    The energy obtained by the $1$st appliance is $1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 2 + 3 + 6 = 11$.
  • 2 2
    The energy obtained by the $2$nd appliance is $1 \cdot 3 = 3$.
  • 1 2 10
    Change the power produced by the $2$nd generator to $10$. The power produced by the generators then become $1$, $10$, and $3$, respectively.
  • 2 1
    The energy obtained by the $1$st appliance is $1 \cdot 10 + 1 \cdot 3 + 10 \cdot 3 = 10 + 3 + 30 = 43$.
  • 2 2
    The energy obtained by the $2$nd appliance is $1 \cdot 3 = 3$.