AT_abc477_e [ABC477E] Wheel Distance

You are given an edge-weighted undirected graph with $ N+1 $ vertices numbered $ 1 $ to $ N+1 $ . For each integer $ i $ satisfying $ 1 \leq i \leq N $ , there is an edge of weight $ A_i $ connecting vertex $ i $ and vertex $ (i \bmod N) + 1 $ . Also, for each integer $ i $ satisfying $ 1 \leq i \leq N $ , there is an edge of weight $ B_i $ connecting vertex $ i $ and vertex $ N+1 $ . There are no other edges. Process $ Q $ queries. In each query, you are given $ S $ and $ T $ ; find the length of the shortest path from vertex $ S $ to vertex $ T $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ B_1 $ $ B_2 $ $ \dots $ $ B_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query $ \mathrm{query}_q $ is given in the following format: > $ S $ $ T $

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

### Sample Explanation 1 For the first query, one shortest path from vertex $ 2 $ to vertex $ 5 $ is $ 2\to1\to5 $ , and its length is $ A_1+A_5=1+5=6 $ . ### Constraints - $ 3 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i, B_i \leq 10^9 $ - $ 1 \leq S \lt T \leq N+1 $ - All input values are integers.