Two Railroads
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 3000
Tags: *special

There are $$$n$$$ cities in Berland, and they are connected by two railroads — the Main railroad and the Auxiliary railroad. Each city has two railway stations, one connected to the Main railroad (called the Main station), and the other connected to the Auxiliary railroad.

The railroads are identical in their structure. The Main railroad consists of $$$n-1$$$ railroad segments; the $$$i$$$-th railroad segment connects the Main station of the city $$$i$$$ with the Main station of the city $$$i+1$$$. Similarly, the Auxiliary railroad consists of $$$n-1$$$ railroad segments; the $$$i$$$-th railroad segment connects the Auxiliary station of the city $$$i$$$ with the Auxiliary station of the city $$$i+1$$$.

These railroads are used to transfer different goods and resources from one city to another. In particular, the Ministry of Energetics is interested in using these railroads to transfer coal.

The Ministry has estimated the following capabilities of the railroads:

- for every $$$i \in [1, n-1]$$$, at most $$$a_i$$$ tons of coal per day can be transferred from the Main station $$$i$$$ to the Main station $$$i+1$$$ (only in this direction);
- for every $$$i \in [1, n-1]$$$, at most $$$b_i$$$ tons of coal per day can be transferred from the Auxiliary station $$$i$$$ to the Auxiliary station $$$i+1$$$ (only in this direction);
- for every $$$i \in [1, n]$$$, at most $$$c_i$$$ tons of coal per day can be transferred from the Main station $$$i$$$ to the Auxiliary station $$$i$$$, or in the opposite direction.

To analyze the capacity of the whole railroad network, the Ministry requires a software that would process and answer queries of the following format:

- calculate the maximum number of tons of coal that can be transferred per day from the Main station $$$l_i$$$ to the Main station $$$r_i$$$.

Your task is to implement this software.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of cities.

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$n-1$$$ integers $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 10^9$$$).

The fourth line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_{n}$$$ ($$$1 \le c_i \le 10^9$$$).

The fifth line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the parameters of the $$$i$$$-th query.

Output format:
Print $$$q$$$ integers, where the $$$i$$$-th integer should be the answer to the $$$i$$$-th query, i. e. the maximum number of tons of coal that can be transferred per day from the Main station $$$l_i$$$ to the Main station $$$r_i$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Example input:
5
3 4 7 4
8 5 3 5
10 5 3 4 10
4
1 4
1 2
3 4
2 4

Example output:
9 8 10 9

Editorial:
Firstly, the problem asks us to find maximum flow in some special network. Instead of the maximum flow, we will try to find the minimum cut for each query.
Recall that an $$$s$$$-$$$t$$$-cut in a flow network is a partition of its vertices into two sets, $$$S$$$ and $$$T$$$, such that $$$s \in S$$$, $$$t \in T$$$, and the total capacity of all arcs leading from a vertex in $$$S$$$ to a vertex in $$$T$$$ is the value of the cut. The maximum flow from $$$s$$$ to $$$t$$$ is equal to the minimum $$$s$$$-$$$t$$$-cut.
Let's analyze the properties of the cut in this network. For simplicity, I will denote the $$$i$$$-th Main station as the vertex $$$v_i$$$, and the $$$i$$$-th Auxiliary station as the vertex $$$u_i$$$.
First of all, if we have a cut where $$$v_i \in S$$$ and $$$v_{i-1} \in T$$$, this cut is not a minimum one. If $$$u_{i - 1} \in S$$$, then we can add $$$v_{i-1}$$$ into $$$S$$$ and remove it from $$$T$$$, so the value of the cut will decrease at least by $$$a_{i-1}$$$. If $$$u_i \notin S$$$, we can remove $$$v_i$$$ from $$$S$$$ and decrease the value of the cut at least by $$$c_i$$$. If both $$$u_i$$$ and $$$v_i$$$ belong to $$$S$$$, and both $$$u_{i-1}$$$ and $$$v_{i-1}$$$ belong to $$$T$$$, we can just remove both $$$u_i$$$ and $$$v_i$$$ from $$$S$$$, and the value of the cut won't increase. So, it means that we can search for a cut where some prefix of vertices on the Main road belongs to $$$S$$$. Similarly, some prefix of vertices on the Auxiliary road will belong to $$$S$$$.
Now there are four cases how the cut can go. They are described in the following pictures:
• Case 1: if the last $$$v$$$-vertex in $$$S$$$ is $$$v_x$$$, then the value of the cut is $$$a_x + c_l + c_{l+1} + \dots + c_{x-1} + c_x$$$, which can be rewritten as $$$a_x + p_x - p_{l-1}$$$. The minimum value can be calculated with a RMQ query of the value $$$a_x + p_x$$$ on the segment $$$[l, r - 1]$$$, since $$$p_{l-1}$$$ is constant.
• Case 2: if the last $$$v$$$-vertex in $$$S$$$ is $$$v_x$$$, then the value of the cut is $$$a_x + c_{x+1} + c_{x+2} + \dots + c_r$$$, which can be rewritten as $$$a_x + p_r - p_x$$$. The minimum value can be calculated with a RMQ query of the value $$$a_x - p_x$$$ on the segment $$$[l, r - 1]$$$, since $$$p_r$$$ is constant.
• Case 3: if the last $$$v$$$-vertex in $$$S$$$ is $$$v_x$$$, and the last $$$u$$$-vertex in $$$S$$$ is $$$u_y$$$, the value of the cut is $$$a_x + b_y + c_{y+1} + c_{y+2} + \dots + c_x = a_x + p_x - b_y - p_y$$$. We need to look deeper into this case, there's no clear way to solve this right now.
• Case 4: similar to Case 3, if we can solve that case, we'll solve Case 4.
Let's analyze the Case 3 more thoroughly. We have to minimize the value of $$$a_x + p_x - b_y - p_y$$$ under the constraints $$$l \le y \le x \le r$$$. Instead of this, let's lift one of the constraints; let's say that $$$y$$$ can be less than $$$l$$$. Then we can easily calculate the minimum value of $$$a_x + p_x - b_y - p_y$$$: for every $$$x$$$, precalculate the minimum $$$b_y + p_y$$$ to the left of it and "match" them; then just use RMQ on the precalculated values.
But doesn't the fact that we have lifted one of the constraints make our solution wrong? In fact, it doesn't. Suppose the answer to the Case 3 is "illegal" because the value of $$$y$$$ we found is less than $$$l$$$. Let's take a look at the picture of this case and the Case 2:
In fact, if Case 3 yields us an illegal solution, it will be overwritten by the solution of Case 2 since an illegal cut for the Case 3 can be transformed into a legal cut for Case 2 (and the value of the cut will only decrease). Similarly, illegal solutions of Case 4 (where we'll lift the constraint $$$y \le r$$$) can be fixed by Case 1.
So, we can answer each query with just four RMQ queries, and our solution runs in, for example, $$$O(n + q \log n)$$$ if we use a segment tree to process RMQ queries.