Cedyks is a good friend of Jiutiaokeli (though they might not be after this contest is public), and he is the protagonist of this problem.

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

Cedyks is a hardworking boy. Every day, he works on different problems to train his The Salt (soul).

One day, he plans to build a city wall around his palace, with $n$ watchtowers on the wall. You can think of 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 the $i$-th watchtower and the $(i+1)$-th watchtower is $w_i$, and the roads between them are bidirectional.

The city wall is soon built, and now Cedyks is planning to build roads from his palace to the wall. Because of the title of this problem, Cedyks intends to measure a construction plan by the sum of the shortest paths from his palace to each watchtower.

Cedyks now has $m$ design plans. The $k$-th design plan will build $T_k$ bidirectional roads between the palace and the watchtowers, where the $i$-th road connects to watchtower $a_i$ with length $l_i$.

Calculating the sum of the shortest paths to every watchtower is a heavy task. Originally, Cedyks wanted to use the widely popular SPFA algorithm to solve it, but because his buffer is too small, he has to turn to the original Bellman-Ford algorithm to calculate it. The general flow of the algorithm is 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 road connecting $u_i$ and $v_i$. Let $d$ be the distance array, initially $d_0 = 0, d_i = 10^{18} (i \in [1, n])$.
2. Let the auxiliary array $c = d$. Sequentially perform relaxation for every edge $(u_i, v_i, w_i)$, where $c_{u_i} = \min(c_{u_i}, d_{v_i} + w_i)$ and $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, i.e., let $S = \{i | c_i \neq d_i\}$, then $t = |S|$. If $t = 0$, it means $d$ is the final shortest path, and the algorithm terminates. Otherwise, set $d = c$ and return to the second step.

Because there are too many design plans to calculate, Cedyks hired some people to help him. To prevent these people from being lazy by fabricating data, he defines the verification value of a design plan as the sum of $t$ each time the Bellman-Ford algorithm enters the third step for this plan. He will have several hired people calculate the same design plan and compare the verification values given by each person.

You are one of the laborers hired by Cedyks. Being clever, you find that calculating the sum of the shortest path lengths in this situation is a very simple matter. However, under the circumstances, you have no choice but to calculate the verification value for each plan to finish the job.

Input

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$ integers $w_i$, representing the length of the road between watchtower $i$ and $i + 1$.

The next $m$ lines each describe a design plan. The first integer $K$ represents the number of roads in the design plan, followed by $K$ pairs $(a_i, l_i)$ representing an edge from the palace to a watchtower.

Output

For each design plan, output one integer per line representing the verification value.

Examples

Input 1

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

Output 1

5
8
5
8
5

Note

• For the first design plan, the changes in $d$ at each stage are: – $[0, 10^{18}, 10^{18}, 10^{18}, 10^{18}, 10^{18}] \to [0, 10^{18}, 2, 10^{18}, 10^{18}, 10^{18}] \to$ – $[0, 4, 2, 5, 10^{18}, 10^{18}] \to [0, 4, 2, 5, 6, 10^{18}] \to [0, 4, 2, 5, 6, 10]$. Therefore, the verification value is $1 + 2 + 1 + 1 = 5$.
• For the second design plan, the changes in $d$ at each stage are: – $[0, 10^{18}, 10^{18}, 10^{18}, 10^{18}, 10^{18}] \to [0, 1, 10^{18}, 10^{18}, 10, 10^{18}] \to$ – $[0, 1, 3, 11, 10, 14] \to [0, 1, 3, 6, 10, 14] \to [0, 1, 3, 6, 7, 14] \to [0, 1, 3, 6, 7, 11]$. Therefore, the verification value is $2 + 3 + 1 + 1 + 1 = 8$.
• For the third design plan, the changes in $d$ at each stage are: – $[0, 10^{18}, 10^{18}, 10^{18}, 10^{18}, 10^{18}] \to [0, 1, 10^{18}, 1, 10^{18}, 1] \to [0, 1, 3, 1, 2, 1]$. Therefore, the verification value is $3 + 1 + 1 = 5$.
• For the fourth design plan, the changes in $d$ at each stage are: – $[0, 10^{18}, 10^{18}, 10^{18}, 10^{18}, 10^{18}] \to [0, 10, 100, 10^{18}, 10^{18}, 1] \to$ – $[0, 10, 12, 103, 5, 1] \to [0, 10, 12, 6, 5, 1] \to [0, 10, 9, 5, 1]$. Therefore, the verification value is $3 + 3 + 1 + 1 = 8$.
• For the fifth design plan, the changes in $d$ at each stage are: – $[0, 10^{18}, 10^{18}, 10^{18}, 10^{18}, 10^{18}] \to [0, 1, 1, 1, 1, 1]$ Therefore, the verification value is $5$.

Constraints

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