After the Vybegallo’s “ideal consumer” incident in the Scientific Research Institute for Thaumaturgy and Spellcraft, an automatic security system is being put into operation urgently. It is to guarantee that in any case the total hyperfield intensity won’t exceed a critical value. They pin hopes on Sasha Privalov and his Aldan machine to automagically process readings of sensors that are located all over the Institute.

All the sensors are numbered with integers ranging from 1 to N (1 ≤ N ≤ 10000). The reading of ith hyperfield intensity sensor is integer k_i (-10000 ≤ k_i ≤ 10000). Aldan is to process quickly queries like "What is the sum of intensities read from the sensors with numbers from i to j (i ≤ j)? The number of queries Q is expected to be rather large (0 ≤ Q ≤ 100000).

The first input line contains integer N. The following N lines contain k_i numbers (one at a line). Then there are the integer Q and Q pairs of numbers i, j (each pair is in a separate line).

should contain Q lines with the sums of the corresponding intensity sensors readings.