Given are N intergers A1...AN.
You will process Q queries on this sequence.
In the i-th query, given two itergers Xi and Yi, find the sum of AXi,AXi+1...AYi.
Constraints
1≤N≤105 1≤Ai≤100 1≤Q≤2×104 1≤Xi≤Yi≤N
Input
N A1…AN Q X1Y1 ⋮ XQYQ
Output
Print Q lines.
The i-th line should contain the response to the i-th query.