32067번 - Game Show 다국어

문제

You are hosting a game show. In your game show, there is a circular disk divided into $N$ regions, numbered from 1ドル$ to $N$ in clockwise order. For each region $i$ (1ドル ≤ i ≤ N - 1$), region $i + 1$ is located to the next of region $i,ドル and region 1ドル$ is located to the next of region $N$.

There are $Q$ independent rounds. In each round, the player starts from region $S$ and the target is at region $T$. For each $i$ such that 1ドル ≤ i ≤ N,ドル the player can move from region $i$ to region $i + 1$ (or to region 1ドル$ if $i = N$) with a penalty of $A_i$. Similarly, the player can move from region $i + 1$ (or from region 1ドル$ if $i = N$) to region $i$ with a penalty of $B_i$. Note that the penalty can be negative.

The goal of each round is to find the minimum total penalty required to reach the target. However, you noticed that it is possible for the player to abuse the game to reach the target with a penalty of $-∞$. Such round is called flawed.

For each round, determine if the round is flawed or not. If the round is not flawed, determine the minimum penalty to reach the target.

입력

Input begins with two integers $N$ $Q$ (3ドル ≤ N ≤ 200,円 000$; 1ドル ≤ Q ≤ 200,円 000$) representing the number of regions and the number of rounds, respectively.

The next line contains $N$ integers $A_i$ ($-10^9 ≤ A_i ≤ 10^9$) representing the penalty to move from region $i$ to region $i + 1,ドル or to region 1ドル$ if $i = N$. The next line contains $N$ integers $B_i$ ($-10^9 ≤ B_i ≤ 10^9$) representing the penalty to move from region $i + 1,ドル or from region 1ドル$ if $i = N,ドル to region $i$.

Each of the next $Q$ lines contains two integers $S$ $T$ (1ドル ≤ S, T ≤ N$) representing the start region and target region of each round, respectively.

출력

For each round, if the round is flawed, then output flawed in a single line. Otherwise, output an integer in a single line, representing the minimum penalty to reach the target.

제한

힌트