AT_abc479_d [ABC479D] Back and Forth Distance

There are $ N $ squares arranged in a row, numbered $ 1, 2, \ldots, N $ from left to right. When you are on square $ i $ , you can make one of the following moves. - Choose an integer $ j $ such that $ 1 \leq j < i $ , and move to square $ j $ . The cost of this move is $ L_i $ . - Choose an integer $ j $ such that $ i < j \leq N $ , and move to square $ j $ . The cost of this move is $ R_i $ . You are given $ Q $ queries. Answer each of them. Each query is in the following format. - Integers $ s $ and $ t $ are given. Find the minimum total cost required to reach square $ t $ from square $ s $ by repeatedly making moves.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ L_2 $ $ L_3 $ $ \ldots $ $ L_N $ $ R_1 $ $ R_2 $ $ \ldots $ $ R_{N - 1} $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ Here, $ \text{query}_i $ is the $ i $ -th query, given in the following format: > $ s $ $ t $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 We explain the first and second queries. For the first query, if you move directly from square $ 1 $ to square $ 2 $ , the total cost is $ R_1 = 3 $ , which is the minimum possible total cost. For the second query, if you move from square $ 2 $ to square $ 4 $ and then from square $ 4 $ to square $ 1 $ , the total cost is $ R_2 + L_4 = 3 $ , which is the minimum possible total cost. ### Constraints - $ 2 \leq N \leq 3 \times 10^5 $ - $ 1 \leq Q \leq 3 \times 10^5 $ - $ 1 \leq L_i \leq 10^9 $ $ (2 \leq i \leq N) $ - $ 1 \leq R_i \leq 10^9 $ $ (1 \leq i \leq N - 1) $ - $ 1 \leq s, t \leq N $ for each query. - $ s \neq t $ for each query. - All input values are integers.