AT_abc477_e [ABC477E] Wheel Distance

頂点に $ 1 $ から $ N+1 $ の番号がついた $ N+1 $ 頂点の辺重み付き無向グラフが与えられます。 $ 1 \leq i \leq N $ を満たす整数 $ i $ について、頂点 $ i $ と頂点 $ (i \bmod N) + 1 $ を結ぶ重み $ A_i $ の辺があります。 また、 $ 1 \leq i \leq N $ を満たす整数 $ i $ について、頂点 $ i $ と頂点 $ N+1 $ を結ぶ重み $ B_i $ の辺があります。これ以外の辺はありません。 $ Q $ 個のクエリを処理してください。クエリでは $ S, T $ が与えられるので、頂点 $ S $ から頂点 $ T $ への最短経路の長さを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 各クエリ $ \mathrm{query}_q $ は以下の形式で与えられる。 > $ S $ $ T $

$ Q $ 行出力せよ。 $ q $ 行目には $ q $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて、頂点 $ 2 $ から頂点 $ 5 $ への最短経路の一つは $ 2\to1\to5 $ であり、その長さは $ 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 $ - 入力される値は全て整数