Description

Cedyks is a rich boy. He lives in the famous The Place (palace).

Cedyks is a hard-working boy. Every day he solves different problems to train his The Salt (soul).

One day, he plans to build a wall around his palace. There are $n$ watchtowers on the wall. You can regard the wall as a line segment, and the watchtowers as $n$ points on the segment, where $1$ and $n$ are the two endpoints of the wall. The distance between watchtower $i$ and watchtower $i + 1$ is $w_i$, and the road between them is bidirectional.

The wall is built soon. Now Cedyks starts planning the roads from his palace to the wall. Because of the problem title, Cedyks decides to measure a construction plan by the sum of the shortest path lengths from his palace to every watchtower.

Now Cedyks has $m$ design plans. In the $k$-th plan, $T_k$ bidirectional roads will be built between the palace and the watchtowers. The $i$-th road connects to watchtower $a_i$ and has length $l_i$.

Computing the sum of shortest paths to every watchtower is heavy work. Originally, Cedyks wanted to use the well-known SPFA algorithm, but because his butter (buffer) is too small, he has to use the primitive Bellman-Ford algorithm instead. The process is roughly as follows:

1. Define the palace as node $0$, and the $i$-th watchtower as node $i$. A bidirectional edge $(u_i, v_i, l_i)$ is a bidirectional road connecting $u_i$ and $v_i$. Let $d$ be the distance array. Initially, $d_0 = 0, d_i = 10^{18}(i ∈ [1, n])$.
2. Let the auxiliary array $c = d$. For each edge $(u_i, v_i, w_i)$ in order, relax it: $c_{u_i} = \min(c_{u_i} , d_{v_i} + w_i)$, $c_{v_i} = \min(c_{v_i} , d_{u_i} + w_i)$.
3. Let $t$ be the number of positions where $c$ and $d$ differ. That is, let $S = \{i|c_i≠d_i\}$, then $t = |S|$. If $t = 0$, it means $d$ is the final shortest path result, and the algorithm ends. Otherwise, set $d = c$ and go back to step 2.

Because there are too many design plans to compute, Cedyks hires some people to help. To prevent them from slacking off with made-up data, he defines the checksum value of a design plan as the sum of $t$ every time the Bellman-Ford algorithm enters step 3 when running on this plan. He will ask several hired people to compute the same plan and compare the checksum values they provide.

You are one of the laborers hired by Cedyks. Being smart, you find that in this situation, computing the sum of shortest path lengths is very easy. However, since you have to obey, you still need to compute the checksum value for each plan to report.

Input Format

The first line contains two integers $n,m$, representing the number of watchtowers and the number of design plans.

The next line contains $n - 1$ numbers $w_i$, representing the length of the road between watchtower $i$ and watchtower $i + 1$.

Then follow $m$ lines, each describing a design plan. The first integer $K$ is the number of roads in the plan. Then follow $K$ pairs $(a_i, l_i)$, each representing an edge from the palace to watchtower $a_i$ with length $l_i$.

Output Format

For each design plan, output one line with one integer, representing the checksum value.

5 5
2 3 1 4
1 2 2
2 1 1 4 10
3 1 1 3 1 5 1
3 1 10 2 100 5 1
5 1 1 2 1 3 1 4 1 5 1

5
8
5
8
5

Hint

Sample Explanation

For the first design plan, the changes of $d$ at each stage are:

• $[0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,10^{18},2,10^{18},10^{18},10^{18}] \rightarrow$ $[0,4,2,5,10^{18},10^{18}] \rightarrow [0,4,2,5,6,10^{18}] \rightarrow [0,4,2,5,6,10]$.

So the checksum value is $1+2+1+1=5$.

For the second design plan, the changes of $d$ at each stage are:

• $[0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,10^{18},10^{18},10,10^{18}] \rightarrow$ $[0,1,3,11,10,14] \rightarrow [0,1,3,6,10,14] \rightarrow [0,1,3,6,7,14] \rightarrow [0,1,3,6,7,11]$.

So the checksum value is $2+3+1+1+1=8$.

For the third design plan, the changes of $d$ at each stage are:

• $[0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,10^{18},1,10^{18},1] \rightarrow [0,1,3,1,2,1]$。

So the checksum value is $3+1+1=5$.

For the fourth design plan, the changes of $d$ at each stage are:

• $[0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,10,100,10^{18},10^{18},1] \rightarrow$ $[0,10,12,103,5,1] \rightarrow [0,10,12,6,5,1] \rightarrow [0,10,9,5,1]$。

So the checksum value is $3+3+1+1=8$.

For the fifth design plan, the changes of $d$ at each stage are:

• $[0,10^{18},10^{18},10^{18},10^{18},10^{18}] \rightarrow [0,1,1,1,1,1]$

So the checksum value is $5$.

Constraints

For $100\%$ of the testdata, it is guaranteed that within each design plan, all $a_i$ are pairwise distinct and $1\le a_i\le n$.
For $100\%$ of the testdata, it is guaranteed that $1\le w_i,l_i\le 10^9,1\le\sum K\le 2\times 10^5$.

Thanks to @Xeonacid for providing the statement.

Translated by ChatGPT 5