I. runnerups
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are working as a sports statistician for a major athletics tournament. Throughout the competition, $$$N$$$ athletes have recorded their performance scores $$$a_1, a_2, \ldots, a_N$$$ in chronological order.

The tournament organizers are interested in analyzing "runner-up excellence" — they want to understand how well the second-best performers did across various event groupings. They will give you $$$Q$$$ analysis requests.

For each request, they specify $$$K$$$ specific time periods (given as indices $$$i_1, i_2, \ldots, i_{K}$$$ in ascending order) that they want to analyze. Your job is to consider every possible subarray that can be formed using these indices as endpoints, find the second-highest score in each subarray, and report the sum of all these runner-up scores.

Input

The first line contains two integers $$$N$$$ ($$$2 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) — the number of athletes and the number of analysis requests respectively. The second line contains $$$N$$$ unique space separated integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — the performance scores. Each of the next $$$Q$$$ lines starts with an integer $$$K$$$ ($$$2 \leq K \leq N$$$) followed by $$$K$$$ strictly increasing integers $$$i_1, i_2, \ldots, i_{K}$$$ ($$$1 \leq i \leq N$$$) — the indices of the time periods to analyze. The sum of all $$$K$$$ values across all queries is at most $$$5 \cdot 10^5$$$.

Output

Output $$$Q$$$ lines. For each analysis request, print the sum of the second-highest scores across all possible subarrays formed using the given indices as endpoints.

Example
Input
9 2
10 12 8 7 4 9 13 15 20
4 2 4 5 9
2 1 9
Output
65
15