Fairy Warehouse Transportation

In the fairy warehouse live the golden fairies, who lead a joyful life and are always ready to sacrifice themselves for this irredeemable world. Meanwhile, the young fairies play games without a care in the world. One day the little fairies invented the following game:

The storage points of the fairy warehouse can be considered as points on a number line. Each storage point (i) is located at (a_i) and contains (x_i) items. The distance between any two storage points is defined by the absolute difference of their positions.

In each round, a group of fairies selects a segment ([l,r]) (that is, storage points with indices from (l) to (r)). The task is to transport all the items from storage points in the segment ([l,r]) to a new warehouse. The cost to transport (x) items from storage point (i) (located at (a_i)) to a destination at (j) is given by

[ \text{cost} = x \times |a_i - j| ]

It can be shown that the total cost is minimized if the destination is chosen as the weighted median of the positions in ([l,r]) (with weights (x_i)). Since the fairies are not good with big numbers, you should output the minimal total cost modulo (19260817).

Input Format:

• The first line contains two integers \(n\) and \(q\): the number of storage points and the number of queries.
• The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the positions of the storage points (in non-decreasing order).
• The third line contains \(n\) integers \(x_1, x_2, \dots, x_n\), where \(x_i\) is the number of items at storage point \(i\).
• Each of the next \(q\) lines contains two integers \(l\) and \(r\), describing a query.

Output Format:

• For each query, output a single line containing the minimum total transportation cost modulo \(19260817\).

Note: For each query, consider the subarray (a_l, a_{l+1}, \dots, a_r) with corresponding weights (x_l, x_{l+1}, \dots, x_r). Compute the optimal cost by choosing a destination such that the sum of the costs (\sum_{i=l}^{r} x_i \times |a_i - j|) is minimized.

inputFormat

• The first line contains two integers \(n\) and \(q\).
• The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\) (positions in non-decreasing order).
• The third line contains \(n\) space‐separated integers \(x_1, x_2, \dots, x_n\) (number of items).
• Each of the next \(q\) lines contains two integers \(l\) and \(r\) representing a query.

outputFormat

• For each query, output a single line containing the minimum total cost modulo \(19260817\).

sample

5 3
1 3 6 7 9
2 1 3 2 1
1 3
2 5
1 5

8
8
27