# MCMF? solution codeforces

## MCMF? solution codeforces

You are given two integer arrays aa and bb (bi0bi≠0 and |bi|109|bi|≤109). 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∑j=lrbj≠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<0bi<0 on the left and those with bi>0bi>0 on right. For each i,ji,j such that li,jrl≤i,j≤rbi<0bi<0 and bj>0bj>0, draw an edge from ii to jj with infinite capacity and cost of unit flow as |aiaj||ai−aj|.
• Add two more vertices: source SS and sink TT.
• For each ii such that lirl≤i≤r and bi<0bi<0, add an edge from SS to ii with cost 00 and capacity |bi||bi|.
• For each ii such that lirl≤i≤r and bi>0bi>0, add an edge from ii to TT with cost 00 and capacity |bi||bi|.
• 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+7109+7.

## MCMF? solution codeforces

If you don’t know what the minimum cost of maximum flow means, read here.

Input

The first line of input contains two integers nn and qq (2n2105,1q2105)(2≤n≤2⋅105,1≤q≤2⋅105)  — length of arrays aabb and the number of queries.

The next line contains nn integers a1,a2ana1,a2…an (0a1a2an109)0≤a1≤a2…≤an≤109)  — the array aa. It is guaranteed that aa is sorted in non-decreasing order.

The next line contains nn integers b1,b2bnb1,b2…bn (109bi109,bi0)(−109≤bi≤109,bi≠0)  — the array bb.

The ii-th of the next qq lines contains two integers li,rili,ri (1lirin)(1≤li≤ri≤n). It is guaranteed that j=liribj=0∑j=liribj=0.

Output

For each query liliriri  — print the cost of subarray a[li:ri]a[li:ri] modulo 109+7109+7.

Example

input

Copy

## MCMF? solution codeforces

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

output
• Contestants ranked 1st will win a Apple HomePod mini
• Contestants ranked 2nd will win a Logitech G903 LIGHTSPEED Gaming Mouse
• Contestants ranked 3rd ~ 5th will win a LeetCode Backpack
• Contestants ranked 6th ~ 10th will win a LeetCode water bottle
• Contestants ranked 11th ~ 20th will win a LeetCode Big O Notebook

Copy

2
0
9
15


Note

## MCMF? solution codeforces

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+|24|1+01=20⋅1+|2−4|⋅1+0⋅1=2.

In the second query, the maximum possible flow is again 11 i.e from source to 7777 to 66, and 66 to sink with a cost of 0|1010|1+01=00⋅|10−10|⋅1+0⋅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⋅3+1⋅1+4⋅2+0⋅1+0⋅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.