Range Shopping

Hamid is visiting a fair near his village. There are N shops of toys arranged in a line from left to right numbered 1 to N. There are two types of toys in each shop. The toy of type 1 costs A[i][0] coins and the toy of type 2 costs A[i][1] coins.

Now, he asks you to solve Q queries for him. Each query will be of type-

l r x y - He visits each shop from l to r in this order and he will buy exactly one toy from each of the visited shops. But, he wants to buy at least x toys of type 1 and at least y toys of type 2. Help him find the minimum cost for buying the toys. Since the answer can be large, return it modulo 10⁹ + 7.

1 <= N, Q <= 10⁵

1 <= l <= r <= N

0 <= x + y <= r-l+1

1 <= A[i][0], A[i][1] <= 10⁹

The first argument contains a 2D array A of size N x 2, denoting the prices of toys.

The second argument contains a 2D array B of size Q x 4, denoting the queires.

Return an array of size Q denoting the answers to the queries. 

Input 1:

  A : 
  [
    [1, 2]
    [4, 2]
    [3, 2]
    [4, 3]
  ]
  B : 
  [
    [2, 3, 1, 1]
    [1, 4, 2, 1]
  ]

  A : 
  [
    [2, 3]
    [4, 5]
    [2, 1]
  ]
  B : 
  [
    [2, 3, 0, 1]
  ]

Output 1:

  [5, 9]

  [5]

Explanation 1:

  1. You can buy toy of type 2 in shop 2 with cost 2 and toy of type 1 in shop 3 with cost 3. 
  2. You can buy toy of type 1 in shop 1 with cost 1, toy of type 2 in shop 2 with cost 3, 
     toy of type 1 in shop 3 with cost 3 and toy of type 2 in shop 4 with cost 3. 
     So, you bought 2 toys of type 1 and 2 toys of type 2.

  Buy toy of type 1 in shop 2 and toy of type 2 in shop 3.