这是一个数学题
题号：NC15096
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

已知有一个n+1个数的数列,对于给定的A0和An ，当i满足当1<=i<=n-1时有 




现在小星想知道对于这个数列一段区间的和。

输入描述:

第一行输入四个数 n,A0,An,Q
接下来Q行 每行输入两个数l,r
0=< n,A0,An<=1e9,Q<=100000
0<=l<=r<=n

输出描述:

对于每组查询输出Al到Ar的和
示例1

输入

复制 
3 0 3 2
1 1
1 3

输出

复制 
1
6

备注:

为了对萌新表现出友好，数据保证了对于Ai的每一项都是整数