At first, this task might seem a bit frightening (for the first task) since it requires you to solve a bunch of queries with very large constraints and Marin's changes on the array elements seem relatively complex. Since this is the first problem called trol, you might suspect that an elegant solution is hiding somewhere.

But, let's start from the beginning. In the test data worth a total of ~20\%~, the queries operate on elements that were not changed by Marin. Therefore, it was enough to output the value of ~l+(l+1)+\dots+(r-1)+r~ for each query.

For an additional ~40\%~, the constraints were such that it was possible to simulate the process explained in the task description. In other words, you could simply loop over the numbers from ~l~ to ~r~ and simulate Marin's changes for each number. The problem of finding the sum of digits of a certain number is well known and well covered (hint: How to obtain the last digit of a number? How to delete the last digit?).

In order to obtain full score on this problem, you needed to make a certain observation. This observation could be made in two ways which we will depict by sharing a couple of truthful anecdotes that occurred during the making of this round.

First way

The task author first told this problem to Marin. Marin is an experienced competitive programmer and he knows that the suggestion for the easiest COCI problem must not be too difficult. Therefore, he conjectured that something fishy must be going on with the array after changes. In a matter of minutes, he implemented the aforementioned solution (worth ~60\%~) and realized that the array is periodic. More precisely, he found out that:

$$\displaystyle A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, \dots\}$$

Marin didn't fully understand why is that the case, but he experimentally proved shown that his conjecture holds.

Second way

The task author then spoke to Stjepan. Stjepan really did recently receive his maths degree so it wasn't long before he remembered something he learned way back in primary school: "The number is divisible by ~9~ if and only if the sum of its digits is divisible by ~9~". He also noted that a stronger formulation also holds, that the remainder we get when dividing a number by ~9~ must equal the remainder we get when we divide the sum of its digits by ~9~. Since that remainder doesn't change when we apply Marin's operation and each positive digit has a distinct remainder, he concluded that we could simply replace each number with a corresponding digit. Then, it is easy to see that the array is periodic in the same way Marin did.

Whether your thought process follows Marin or Stjepan, one thing is certain, once you made this observation the task became easy. Suppose we divide the numbers from the query in consecutive blocks of size ~9~. It is easy to see that each block has the same sum which equals ~1+2+\dots+9 = 45~. There is a total of ~\lfloor \frac{r-l+1}{9} \rfloor~ complete blocks. We still need to add the elements from the final, incomplete block. The number of elements in that block is ~(r-l+1) \bmod 9~ and the first number is ~l~. Therefore, we can answer each query in ~\mathcal O(1)~.