AT_abc479_d [ABC479D] Back and Forth Distance

$ N $ 個のマスが一直線上に並んでおり、左から順に $ 1, 2, \ldots, N $ の番号が付いています。 あなたがマス $ i $ にいるとき、以下のいずれかの移動をすることができます。 - $ 1 \leq j < i $ なる整数 $ j $ を選び、マス $ j $ に移動する。この移動にはコストが $ L_i $ かかる。 - $ i < j \leq N $ なる整数 $ j $ を選び、マス $ j $ に移動する。この移動にはコストが $ R_i $ かかる。 $ Q $ 個のクエリが与えられます。それぞれについて答えてください。各クエリは以下の形式です。 - 整数 $ s, t $ が与えられる。あなたがマス $ s $ から移動を繰り返してマス $ t $ に辿り着くまでに必要なコストの合計の最小値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ ただし、 $ \text{query}_i $ は $ i $ 番目のクエリであり、以下の形式で与えられる。 > $ s $ $ t $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1, 2 $ 番目のクエリについて説明します。 $ 1 $ 番目のクエリでは、マス $ 1 $ から直接マス $ 2 $ に移動したとき、コストの合計は $ R_1 = 3 $ となり、これがコストの合計として考えられる最小値になります。 $ 2 $ 番目のクエリでは、マス $ 2 $ からマス $ 4 $ に移動し、その後マス $ 4 $ からマス $ 1 $ に移動したとき、コストの合計は $ R_2 + L_4 = 3 $ となり、これがコストの合計として考えられる最小値になります。 ### 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 $ - 各クエリについて $ s \neq t $ - 入力される値はすべて整数