A15131 | MCMF?

You are given two integer arrays $a$ and $b$ ( $b_i \neq 0$ and $|b_i| \leq 10^9$ ). Array $a$ is sorted in non-decreasing order.

The cost of a subarray $a[l:r]$ is defined as follows:

- If $ \sum\limits_{j = l}^{r} b_j \neq 0$ , then the cost is not defined.
- Otherwise:


- Construct a bipartite flow graph with $r-l+1$ vertices, labeled from $l$ to $r$ , with all vertices having $b_i \lt 0$ on the left and those with $b_i \gt 0$ on right. For each $i, j$ such that $l \le i, j \le r$ , $b_i<0$ and $b_j>0$ , draw an edge from $i$ to $j$ with infinite capacity and cost of unit flow as $|a_i-a_j|$ .
- Add two more vertices: source $S$ and sink $T$ .
- For each $i$ such that $l \le i \le r$ and $b_i<0$ , add an edge from $S$ to $i$ with cost $0$ and capacity $|b_i|$ .
- For each $i$ such that $l \le i \le r$ and $b_i>0$ , add an edge from $i$ to $T$ with cost $0$ and capacity $|b_i|$ .
- The cost of the subarray is then defined as the minimum cost of maximum flow from $S$ to $T$ .

You are given $q$ queries in the form of two integers $l$ and $r$ . You have to compute the cost of subarray $a[l:r]$ for each query, modulo $10^9 + 7$ .

If you don't know what the minimum cost of maximum flow means, read [here](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem).

The first line of input contains two integers $n$ and $q$ $(2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5)$ — length of arrays $a$ , $b$ and the number of queries.

The next line contains $n$ integers $a_1,a_2 \ldots a_n$ ( $0 \leq a_1 \le a_2 \ldots \le a_n \leq 10^9)$ — the array $a$ . It is guaranteed that $a$ is sorted in non-decreasing order.

The next line contains $n$ integers $b_1,b_2 \ldots b_n$ $(-10^9\leq b_i \leq 10^9, b_i \neq 0)$ — the array $b$ .

The $i$ -th of the next $q$ lines contains two integers $l_i,r_i$ $(1\leq l_i \leq r_i \leq n)$ . It is guaranteed that $ \sum\limits_{j = l_i}^{r_i} b_j = 0$ .

For each query $l_i$ , $r_i$ — print the cost of subarray $a[l_i:r_i]$ modulo $10^9 + 7$ .