Description

Golden fairies live in the Fairy Warehouse. They live happily, yet are always ready to face death.

Put more nobly, they are always ready to sacrifice themselves for this hopeless world.

However, children always live carefree lives. The young golden fairies live innocently and naturally have no time to think about heavy duties like saving the world.

One day, the little fairies are playing a game again. The game goes like this.

The storage points of the Fairy Warehouse can be regarded as lying on a number line. Each storage point has some items, and there are distances between them.

Each time they pick one little fairy, and the others collect all the items at the storage points in the interval $[l, r]$. After counting, they ask her: what is the cost to move all items from storage points in this interval to another storage point?

For example, if storage point $i$ has $x$ items and you want to move them to storage point $j$, the cost is

Here, $\mathrm{dist}$ is the distance between storage points.

Of course, since the little fairies cannot handle very large numbers, your answer needs to be taken modulo $19260817$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n-1$ integers. The $i$-th number is the distance between storage points $i$ and $i+1$.

The third line contains $n$ integers, giving the number of items at each storage point.

Then follow $m$ lines, each containing three integers x l r.

Each query asks for the cost to move all items from storage points in the interval $[l, r]$ to storage point $x$.

Output Format

For each query, output one integer: the answer.

5 5
2 3 4 5
1 2 3 4 5
1 1 5
3 1 5
2 3 3
3 3 3
1 5 5

125
72
9
0
70

Hint

• For $30\%$ of the testdata, $n, m \le 1000$.
• For another $20\%$ of the testdata, all distances between storage points are $1$.
• For another $20\%$ of the testdata, the number of items at every storage point is $1$.
• For $100\%$ of the testdata, $n, m \le 200000$; all distances and item counts are at most $2 \cdot 10^9$.

Translated by ChatGPT 5