F1. Timosh and Subarrays #1 Upsolve
In a small school, Timosh and his friends organized a competition to quickly find the sum of elements of subarrays with different lengths. Timosh used a simple method that worked well for small arrays. Now, help Timosh by writing a program that solves this problem quickly.
You are given an array of n numbers and a series of queries. For each query:
- You are given a number k. Calculate the sum of all subarrays of length k.
Input
The first line contains an integer, n(1≤n≤2∗105).
The second line contains numbers separated by spaces, ai(1≤ai≤105).
The third line contains the number of queries, q(1≤q≤2∗105).
The next q lines contain the queries, ki(1≤ki≤n).
Output
Output the answer for each query on a separate line.
Sample input 1
5 1 2 3 4 5 3 1 3 5
Sample output 1
15 27 15