#P1682F. MCMF?
MCMF?
Description
You are given two integer arrays and ( and ). Array is sorted in non-decreasing order.
The cost of a subarray is defined as follows:
If , then the cost is not defined.
Otherwise:
- Construct a bipartite flow graph with vertices, labeled from to , with all vertices having on the left and those with on right. For each such that , and , draw an edge from to with infinite capacity and cost of unit flow as .
- Add two more vertices: source and sink .
- For each such that and , add an edge from to with cost and capacity .
- For each such that and , add an edge from to with cost and capacity .
- The cost of the subarray is then defined as the minimum cost of maximum flow from to .
You are given queries in the form of two integers and . You have to compute the cost of subarray for each query, modulo .
If you don't know what the minimum cost of maximum flow means, read here.
The first line of input contains two integers and — length of arrays , and the number of queries.
The next line contains integers ( — the array . It is guaranteed that is sorted in non-decreasing order.
The next line contains integers — the array .
The -th of the next lines contains two integers . It is guaranteed that .
For each query , — print the cost of subarray modulo .
Input
The first line of input contains two integers and — length of arrays , and the number of queries.
The next line contains integers ( — the array . It is guaranteed that is sorted in non-decreasing order.
The next line contains integers — the array .
The -th of the next lines contains two integers . It is guaranteed that .
Output
For each query , — print the cost of subarray modulo .
Samples
Note
In the first query, the maximum possible flow is i.e one unit from source to , then one unit from to , then one unit from to sink. The cost of the flow is .
In the second query, the maximum possible flow is again i.e from source to , to , and to sink with a cost of .
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.
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.