## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] MCMF? Codeforces Solution | Codeforces Problem Solution 2022

F. MCMF?
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integer arrays $a$ and $b$ (${b}_{i}\ne 0$ and $|{b}_{i}|\le {10}^{9}$). Array $a$ is sorted in non-decreasing order.

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

• If $\sum _{j=l}^{r}{b}_{j}\ne 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}<0$ on the left and those with ${b}_{i}>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}|$.

Input

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

The next line contains $n$ integers ${a}_{1},{a}_{2}\dots {a}_{n}$ ($0\le {a}_{1}\le {a}_{2}\dots \le {a}_{n}\le {10}^{9}\right)$  — the array $a$. It is guaranteed that $a$ is sorted in non-decreasing order.

The next line contains $n$ integers ${b}_{1},{b}_{2}\dots {b}_{n}$ $\left(-{10}^{9}\le {b}_{i}\le {10}^{9},{b}_{i}\ne 0\right)$  — the array $b$.

The $i$-th of the next $q$ lines contains two integers ${l}_{i},{r}_{i}$ $\left(1\le {l}_{i}\le {r}_{i}\le n\right)$. It is guaranteed that $\sum _{j={l}_{i}}^{{r}_{i}}{b}_{j}=0$.

Output

For each query ${l}_{i}$${r}_{i}$  — print the cost of subarray $a\left[{l}_{i}:{r}_{i}\right]$ modulo ${10}^{9}+7$.