#P1682F. MCMF?

    ID: 7782 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>data structuresflowsgraphsgreedysortingstwo pointers

MCMF?

Description

You are given two integer arrays aa and bb (bi0b_i \neq 0 and bi109|b_i| \leq 10^9). Array aa is sorted in non-decreasing order.

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

  • If j=lrbj0 \sum\limits_{j = l}^{r} b_j \neq 0, then the cost is not defined.

  • Otherwise:

    • Construct a bipartite flow graph with rl+1r-l+1 vertices, labeled from ll to rr, with all vertices having bi<0b_i \lt 0 on the left and those with bi>0b_i \gt 0 on right. For each i,ji, j such that li,jrl \le i, j \le r, bi<0b_i<0 and bj>0b_j>0, draw an edge from ii to jj with infinite capacity and cost of unit flow as aiaj|a_i-a_j|.
    • Add two more vertices: source SS and sink TT.
    • For each ii such that lirl \le i \le r and bi<0b_i<0, add an edge from SS to ii with cost 00 and capacity bi|b_i|.
    • For each ii such that lirl \le i \le r and bi>0b_i>0, add an edge from ii to TT with cost 00 and capacity bi|b_i|.
    • The cost of the subarray is then defined as the minimum cost of maximum flow from SS to TT.

You are given qq queries in the form of two integers ll and rr. You have to compute the cost of subarray a[l:r]a[l:r] for each query, modulo 109+710^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 nn and qq (2n2105,1q2105)(2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5)  — length of arrays aa, bb and the number of queries.

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

The next line contains nn integers b1,b2bnb_1,b_2 \ldots b_n (109bi109,bi0)(-10^9\leq b_i \leq 10^9, b_i \neq 0)  — the array bb.

The ii-th of the next qq lines contains two integers li,ril_i,r_i (1lirin)(1\leq l_i \leq r_i \leq n). It is guaranteed that j=liribj=0 \sum\limits_{j = l_i}^{r_i} b_j = 0.

For each query lil_i, rir_i  — print the cost of subarray a[li:ri]a[l_i:r_i] modulo 109+710^9 + 7.

Input

The first line of input contains two integers nn and qq (2n2105,1q2105)(2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5)  — length of arrays aa, bb and the number of queries.

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

The next line contains nn integers b1,b2bnb_1,b_2 \ldots b_n (109bi109,bi0)(-10^9\leq b_i \leq 10^9, b_i \neq 0)  — the array bb.

The ii-th of the next qq lines contains two integers li,ril_i,r_i (1lirin)(1\leq l_i \leq r_i \leq n). It is guaranteed that j=liribj=0 \sum\limits_{j = l_i}^{r_i} b_j = 0.

Output

For each query lil_i, rir_i  — print the cost of subarray a[li:ri]a[l_i:r_i] modulo 109+710^9 + 7.

Samples

样例输入 1

8 4
1 2 4 5 9 10 10 13
6 -1 1 -3 2 1 -1 1
2 3
6 7
3 5
2 6

样例输出 1

2
0
9
15

Note

In the first query, the maximum possible flow is 11 i.e one unit from source to 22, then one unit from 22 to 33, then one unit from 33 to sink. The cost of the flow is 01+241+01=20 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2.

In the second query, the maximum possible flow is again 11 i.e from source to 77, 77 to 66, and 66 to sink with a cost of 010101+01=00 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0.

In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.

Maximum flow is 33 with a cost of 03+11+42+01+02=90 \cdot 3 + 1 \cdot 1 + 4 \cdot 2 + 0 \cdot 1 + 0 \cdot 2 = 9.

In the fourth query, the flow network looks as –

The minimum cost maximum flow is achieved in the configuration –

The maximum flow in the above network is 4 and the minimum cost of such flow is 15.