409010: GYM103415 B Sweeping Robots

There are $$$n$$$ sweeping robots in a line, and the $$$i$$$-th robot from left to right has a cost $$$c_i$$$. It is guaranteed that all $$$c_i$$$'s are distinct. The distance between the $$$i$$$-th robot and the $$$(i{+}1)$$$-th robot is $$$d_i$$$.

When you want to sweep the interval between the $$$l$$$-th robot and the $$$r$$$-th robot, you will first greedily choose the robot with the minimal cost in that interval. Then, the robot will find a path that covers every robot in that interval at least once, with a length as minimal as possible. Note that the robot does not need to return to the original place. Define the cost of interval $$$[l,r]$$$ as the cost of the selected robot multiplies the length of the selected path.

You need to answer $$$q$$$ queries, and each query is as follow: for a given interval $$$[l,r]$$$, what is the maximal cost over intervals $$$[l',r']$$$ such that $$$l \le l' \le r' \le r$$$?

The first line consists of an integer $$$n$$$ ($$$1 \le n \le 5 \times 10^5$$$).

The second line consists of $$$n$$$ integers, the $$$i$$$-th of which is $$$c_i$$$ ($$$1 \le c_i \le n$$$).

The third line consists of $$$n-1$$$ integers, the $$$i$$$-th of which is $$$d_i$$$ ($$$1 \le d_i \le 10^5$$$).

The fourth line consists of an integer $$$q$$$ ($$$1 \le q \le 10^6$$$).

The next $$$q$$$ lines describes the queries, and the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

The output is large, so you only need to print $$$1$$$ integer — The XOR sum of the $$$q$$$ integers, the $$$i$$$-th of which should be the answer for interval $$$[l_i,r_i]$$$.

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

18