Problem Background

City H is a megacity with a constant flow of passengers traveling across its various corners. The suburban areas of the city are sparsely built, and to facilitate travel for the local population, the city has constructed a suburban railway parallel to the main highway, complementing the bus system on the road. The railway stations and bus stops in the same direction do not fully align but include several transfer stations where both trains and buses stop. Currently, the suburban railway operates a single one-way train during the morning and evening rush hours.

The diagram above shows the schematic of the suburban railway and bus stops in the morning rush hour direction. The blue arrows connect the transfer stations where suburban railway passengers can transfer to buses.

In the following problem, we ignore the existence of non-transfer stations and only consider the impact of transfer stations during operations.

Problem Description

Due to the increase in city population, the commuting pressure on the suburban railway in City H has increased. To cope with the short-term large passenger flow, the bus group has decided to arrange several bus services on a certain bus route during the morning rush hour, with the same direction as the train, running from west to east, facilitating train passengers to transfer to buses to reach their destinations.

Given a street with a total of $n$ transfer stations, numbered from west to east as $1$ to $n$. Each transfer station has a different level of emphasis on operational efficiency, denoted as $v_i$ for the $i$-th transfer station. The travel time for different buses between the same intervals is the same, with the time to travel from the $i$-th transfer station to the $i+1$-th transfer station being $s_i$, ignoring the time spent at stops. The suburban railway train arrives at the $i$-th transfer station at time $t_i$. It is guaranteed that the time spent on the bus between two transfer stations is never less than the time spent on the suburban railway.

You need to arrange $k$ bus services on this bus route. All $n$ transfer stations will have passengers disembarking from the railway. For each bus, you need to specify its departure time and departure transfer station, ensuring that passengers from any transfer station can catch a bus, i.e., the latest arrival time of the bus at transfer station $i$ must not be earlier than $t_i$. Each bus, once departed, will travel eastward to the $n$-th transfer station at a fixed speed, stopping at each station along the way to pick up waiting passengers. You can arbitrarily designate the starting station and departure time for each bus route.

Passengers will board the first bus that arrives at their station after they arrive. The dissatisfaction at transfer station $i$ is defined as the product of the waiting time of passengers who disembark from the railway at time $t_i$ and the emphasis level of the starting station of the bus they board. If multiple buses arrive simultaneously, passengers will board the bus with the lowest emphasis level. You need to minimize the sum of dissatisfaction across all $n$ transfer stations.

The railway timetable and the number of available buses for the bus company are always changing, so you need to handle multiple queries with different $t_i$ and $k$.

Input Format

The first line contains a positive integer $n$, the number of transfer stations.

The second line contains $n-1$ space-separated non-negative integers $s_1, s_2, ..., s_{n-1}$.

The third line contains $n$ space-separated non-negative integers $v_i$.

The fourth line contains a positive integer $p$, the number of different suburban railway timetables.

The following contains $p$ sets of data, each set consisting of three lines.

The first line of each set contains $n$ space-separated positive integers $t_1, t_2, ..., t_n$.

The second line of each set contains a positive integer $q_i$, the number of queries for $k$ under the current timetable.

The third line of each set contains $q_i$ space-separated positive integers $k_1, k_2, ..., k_q$, the different values of $k$ for the queries.

Output Format

Output $p$ lines, each line containing $q_i$ space-separated positive integers, representing the minimum sum of dissatisfaction for all transfer stations under the current query's $k$.

Sample Input and Output

Input Sample #1

3
3 4
6 2 1
2
1 3 7
2
1 2
2 3 5
3
1 2 4

Output Sample #1

12 0
36 4 0

Input Sample #2

6
2 2 2 2 3
13 12 15 9 3 1
3
5 7 9 11 12 13
4
1 2 4 8
3 4 5 7 8 10
3
2 4 5
1000000 1000001 1000002 1000003 1000004 1000005
2
1 3

Output Sample #2

52 6 0 0
49 3 0
208 31

Notes/Hints

[Data Range]

For all test cases, it is guaranteed that $1 \leq n \leq 1000$, $1 \leq p \leq 10$, $s_i \geq t_{i+1} - t_i \geq 0$, $1 \leq q_i, k_i \leq 10^6$, $0 \leq v_i, \sum s_i \leq 10^6$, $1 \leq t_i \leq 2 \times 10^6$.

This problem uses bundled testing.

Special Condition $A$: For all inputs, it is guaranteed that $s_i = t_{i+1} - t_i$.

Special Condition $B$: It is guaranteed that $v_i = 1$.

[Sample Explanation]

Below is a feasible optimal dispatch plan for each query in Sample 1. Note that there may be multiple optimal solutions.

For the first timetable in Sample 1:
- When $k = 1$, we dispatch a bus at time $1$ from station $1$, with the following operational details:
| | Station $1$ | Station $2$ | Station $3$ |
| :-----------------: | :---------: | :---------: | :---------: |
| Railway Arrival Time| $1$ | $3$ | $7$ |
| Bus $1$ Arrival Time| $1$ | $4$ | $8$ |
| Boarding Bus | Bus $1$ | Bus $1$ | Bus $1$ |
| Passenger Wait Time | $0$ | $1$ | $1$ |

The starting station for Bus $1$ is station $1$, with $v_1 = 6$. Thus, the final answer is $6 \times 0 + 6 \times 1 + 6 \times 1 = 12$.

• When $k = 2$, we dispatch a bus at time $1$ from station $1$ and at time $3$ from station $2$, with the following operational details:
  | | Station $1$ | Station $2$ | Station $3$ |
  | :-----------------: | :---------: | :---------: | :---------: |
  | Railway Arrival Time| $1$ | $3$ | $7$ |
  | Bus $1$ Arrival Time| $1$ | $4$ | $8$ |
  | Bus $2$ Arrival Time| / | $3$ | $7$ |
  | Boarding Bus | Bus $1$ | Bus $2$ | Bus $2$ |
  | Passenger Wait Time | $0$ | $0$ | $0$ |

The starting station for Bus $1$ is station $1$, with $v_1 = 6$; for Bus $2$, it is station $2$, with $v_2 = 2$. Thus, the final answer is $6 \times 0 + 2 \times 0 + 2 \times 0 = 0$.

For the second timetable in Sample 1:
- When $k = 1$, we dispatch a bus at time $2$ from station $1$, with the following operational details:
| | Station $1$ | Station $2$ | Station $3$ |
| :-----------------: | :---------: | :---------: | :---------: |
| Railway Arrival Time| $2$ | $3$ | $5$ |
| Bus $1$ Arrival Time| $2$ | $5$ | $9$ |
| Boarding Bus | Bus $1$ | Bus $1$ | Bus $1$ |
| Passenger Wait Time | $0$ | $2$ | $4$ |

The starting station for Bus $1$ is station $1$, with $v_1 = 6$. Thus, the final answer is $6 \times 0 + 6 \times 2 + 6 \times 4 = 36$.

• When $k = 2$, we dispatch a bus at time $2$ from station $1$ and at time $3$ from station $2$, with the following operational details:
  | | Station $1$ | Station $2$ | Station $3$ |
  | :-----------------: | :---------: | :---------: | :---------: |
  | Railway Arrival Time| $2$ | $3$ | $5$ |
  | Bus $1$ Arrival Time| $2$ | $5$ | $9$ |
  | Bus $2$ Arrival Time| / | $3$ | $7$ |
  | Boarding Bus | Bus $1$ | Bus $2$ | Bus $2$ |
  | Passenger Wait Time | $0$ | $0$ | $2$ |

The starting station for Bus $1$ is station $1$, with $v_1 = 6$; for Bus $2$, it is station $2$, with $v_2 = 2$. Thus, the final answer is $6 \times 0 + 2 \times 0 + 2 \times 2 = 4$.

• When $k = 4$, we dispatch buses at times $-2$ and $2$ from station $1$, and at times $1$ and $3$ from station $2$, with the following operational details:
  | | Station $1$ | Station $2$ | Station $3$ |
  | :-----------------: | :---------: | :---------: | :---------: |
  | Railway Arrival Time| $2$ | $3$ | $5$ |
  | Bus $1$ Arrival Time| $-2$ | $1$ | $5$ |
  | Bus $2$ Arrival Time| $2$ | $5$ | $9$ |
  | Bus $3$ Arrival Time| / | $1$ | $5$ |
  | Bus $4$ Arrival Time| / | $3$ | $7$ |
  | Boarding Bus | Bus $2$ | Bus $4$ | Bus $3$ |
  | Passenger Wait Time | $0$ | $0$ | $0$ |

The starting stations for Buses $1$ and $2$ are station $1$, with $v_1 = 6$; for Buses $3$ and $4$, they are station $2$, with $v_2 = 2$. Thus, the final answer is $6 \times 0 + 2 \times 0 + 2 \times 0 = 0$.

Note that for station $3$, Buses $1$ and $3$ arrive simultaneously, but since Bus $1$ has an emphasis level $v_1 = 6$ and Bus $3$ has an emphasis level $v_2 = 2$, passengers board Bus $3$.

见题面 Input 部分

见题面 Output 部分