Description

国庆期间，各地车流量陡增，交通部门在高速公路沿途设置监测点，观察堵车情况。以沪蓉高速为例，总长\(1966\)千米，每隔\(1\)千米设置一个监测点，以小时为单位记录每个监测点的流量。为提升交通管理效率，请编写程序计算任意两个监测点之间的车流量。

Format

Input

第一行，\(1967\)个数据，表示从上高速到下高速之间每个监测点的车流量数据。

第二行，一个正整数\(n\)，表示有\(n\)个问题。

接下来\(n\)行，每行两个正整数\(l\)和\(r\)，表示询问从\(l\)到\(r\)之间的总车流量。

Output

共\(n\)行，每行一个正整数，回答\(l\)到\(r\)之间的总车流量。

Sample 1

Input

1 1 1 .....(1967个1)
3
1 1
1 3
1 1966

Output

1
3
1966

Limitation&Appointment

对于\(30\%\)的数据，\(n \le 100\)
对于\(100\%\)的数据，\(n \le 2 \times10^5\)，每个监测点的车流量不大于\(10^9\)。

共\(10\)个测试点，对于每一个测试点，时间限制为\(1000 ms\)，空间限制为\(128 MiB\)，分值为\(10\)分。