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.

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$.