P4433 [COCI 2009/2010 #1] ALADIN

You are given $n$ boxes and $q$ operations of two types: - Type 1 operation with input format `1 L R A B`: for each box $X$ with $L \leq X \leq R$, set its number of stones to $(X - L + 1) \times A \bmod B$, where $X$ is the index of the box. - Type 2 operation with input format `2 L R`: query the total number of stones in boxes numbered $L$ through $R$.

The first line contains two integers $n$ ($1 \leq n \leq 10^9$) and $q$ ($1 \leq q \leq 5 \times 10^4$). The next $q$ lines describe the operations.

For each type 2 operation, output the total number of stones.

- For $30\%$ of the testdata, $n, q \leq 10^3$. - For $70\%$ of the testdata, $q \leq 10^3$. - For $100\%$ of the testdata, $1 \leq A, B \leq 10^6$. Translated by ChatGPT 5