P3932 No. 68 Island of the Floating Continent

Island No. $68$ of the Floating Continent is located in the borderlands of the Floating Continent. It is rarely visited. The island is covered by dense forest.  On this unremarkable floating island at the border, there is a mysterious “weapon” management depot — the Fairy Warehouse.

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 $$x \times \mathrm{dist}( i , j ).$$ 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$. 

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$.

For each query, output one integer: the answer.

- 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