P15628 [ICPC 2022 Jakarta R] 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 \leq i \leq 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 \leq i \leq 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 $-\infty$. 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 \leq N \leq 200\,000$; $1 \leq Q \leq 200\,000$) representing the number of regions and the number of rounds, respectively. The next line contains $N$ integers $A_i$ ($-10^9 \leq A_i \leq 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 \leq B_i \leq 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 \leq S, T \leq 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.

#### Explanation for the sample input/output #1 In round $1$, the path $1 \rightarrow 2 \rightarrow 3$ has a penalty of $2 + 3 = 5$. In round $2$, the path $3 \rightarrow 4 \rightarrow 1$ has a penalty of $(-4) + 3 = -1$. This path has lesser penalty than path $3 \rightarrow 2 \rightarrow 1$, which has a penalty of $2 + 1 = 3$. In round $3$, the path $1 \rightarrow 4$ has a penalty of $-1$. #### Explanation for the sample input/output #2 For all rounds, the player can go to region $2$, then repeatedly travel back and forth in regions $2$ and $3$ to reduce the penalty by $1$ infinitely many times.