AT_abc423_e [ABC423E] Sum of Subarrays

You are given an integer sequence $ A = (A_1, A_2, \ldots, A_N) $ of length $ N $ . $ Q $ queries are given, so find the answer for each. In the $ i $ -th query, integers $ L_i $ and $ R_i $ are given, so find $ \displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j $ as the answer.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 We explain the first query. The value to be calculated is $ \displaystyle\sum_{l = 2}^{4}\sum_{r = l}^{4}\sum_{j = l}^{r} A_j $ . - When $ l = 2, r = 2 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 1 $ . - When $ l = 2, r = 3 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 4 $ . - When $ l = 2, r = 4 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 7 $ . - When $ l = 3, r = 3 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 3 $ . - When $ l = 3, r = 4 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 6 $ . - When $ l = 4, r = 4 $ , $ \displaystyle\sum_{j = l}^{r} A_j = 3 $ . From the above, the value to be calculated is $ (1 + 4 + 7) + (3 + 6) + 3 = 24 $ . ### Constraints - $ 1 \leq N, Q \leq 3 \times 10^5 $ - $ 1 \leq A_i \leq 100 $ - $ 1 \leq L_i \leq R_i \leq N $ - All input values are integers.