A park ranger patrols a straight ridge trail lined with n numbered checkpoints, positioned in order 1 through n. Inspecting checkpoint i takes c_i minutes. Walking directly from checkpoint i to checkpoint i+1 (for 1 <= i <= n-1) takes h_i minutes. Over the course of a day the ranger receives q separate tour requests. For the j-th request, given as a range [l, r] with l <= r, the ranger starts already standing at checkpoint l, inspects checkpoints l, l+1, ..., r one after another in increasing order (walking between each consecutive pair of checkpoints along the way), and stops immediately once checkpoint r has been inspected — no walk back and no other checkpoints are visited. For every request, report how many minutes that tour takes in total: the sum of the inspection times of every checkpoint from l to r, plus the sum of the walking times between every pair of consecutive checkpoints from l to r.

Input format

• Line 1: a single integer n.
• Line 2: n space-separated integers c_1 ... c_n.
• Line 3: n - 1 space-separated integers h_1 ... h_{n-1} (this line contributes no numbers, and may be blank, when n = 1).
• Line 4: a single integer q.
• Each of the next q lines contains two space-separated integers l and r describing one tour request.

Output format

Print q lines. The j-th line must contain the total duration, in minutes, of the j-th tour request.

Constraints

• 1 <= n <= 10^5
• 1 <= c_i <= 10^4
• 1 <= h_i <= 10^4
• 1 <= q <= 10^5
• 1 <= l <= r <= n

4
5 3 8 2
1 4 2
2
1 4
2 3

25
15

1
7
1
1 1

7