B. Hungry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hendy is hungry and wants to eat asandwich. He has two options:

  • Go to the shop in $$$x$$$ minutes, then wait in the queue until he gets his order.
  • Order his food by delivery, but the shop has a rule: the shop will serve the first $$$m$$$ people in the queue, then deliver the order in $$$y$$$ minutes.

Currently, there are $$$n$$$ customers in the queue, and it takes $$$a_{i}$$$ $$$(1\leq i \leq n)$$$ minutes to serve the $$$i_{th}$$$ customer (the shop serves only one customer at once).

Assume that the shop won't take time to prepare the food and there won't be any new customers after the current $$$n$$$ customers.

You are given $$$q$$$ queries. For each query, you are given $$$x$$$,$$$y$$$ ,and $$$m$$$. For each query, you have to find the minimum time required for Hendy to get his food.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{5})- $$$the number of customers in the queue.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}-$$$ time to serve the $$$i_{th}$$$ customer.

The third line contains $$$q$$$ $$$(1 \leq q \leq 10^{5})- $$$the number of queries.

The next $$$q$$$ lines contain three integers $$$x$$$, $$$y$$$ $$$(1\leq x,y \leq 10^{9})$$$ and $$$m$$$ $$$(1 \leq m \leq n)- $$$the time to reach the shop, time to deliver the order, and the number of customers the shop will serve before delivering the order, respectively.

Output

For each query , print a single line that is the answer to the problem.

Example
Input
5
1 2 1 3 4
5
3 4 3
5 10 2
1 3 3
10 4 2
15 10 5
Output
8
11
7
7
15