We will arrive at a solution to this problem in several steps. Let us first simplify the problem.

Notice that each operation has an inverse operation, which is of the same type, but with the opposite sign, that is, rotating in the opposite direction. This means that we can obtain the starting sequence by applying inverses of the input operations, in reverse order, to the final sequence.

Also, notice that any rotation to the left can be replaced with an equivalent rotation to the right. Rotation of the whole sequence by ~X~ to the left can be replaced by a rotation of the sequence by ~N-X~ to the right; analogously for section rotations.

The next simplification is replacing the numbers in the sequence with their positions, and then applying operations to the position sequence. It is easy to restore the original numbers from the positions after finishing with the rotations.

The problem has been reduced to starting with the sequence ~(0, 1, \dots, N-1)~ and applying 2 types of rotation-to-the-right operations to it. A simple simulation of each operation leads to the complexity ~\mathcal O(NQ)~, which is sufficient for ~40\%~ of total points.

Looking at numbers ~A~ and ~A+K~ (modulo ~N~), observe that their distance (modulo ~N~) remains equal to ~K~ after any rotation operation. Therefore, it is sufficient to track only the positions of numbers ~(0, 1, \dots, K-1)~ while applying rotations. In the end, the positions of the remaining numbers can be reconstructed as follows: ~pos[A] = (pos[A \bmod K] + A / K \times K) \bmod K~.

This improved simulation of each operation has the complexity ~\mathcal O(KQ)~, which is sufficient for ~70\%~ of total points.

For further optimization, we can track the positions of the numbers ~(0, 1, \dots, K-1)~ (modulo ~K~). After each operation, their positions are some rotation of the general form: ~B, B+1, \dots, K-1, 0, 1, \dots, B-1~. This rotation can be tracked by a single global variable representing the total number of rotations to the right needed to transform the starting sequence of positions to the current one. Both types of rotations to the right simply add ~X~ to this total rotation. Thus, the position of each of the first ~K~ numbers in its current section is easily obtainable from the total rotation.

To unambiguously determine the position of the first ~K~ numbers, and by extension all ~N~ numbers, we also need to track the current section for each of the ~K~ numbers.

An operation of type 1 doesn't change the contents of the sections. An operation of type 2 can be processed modulo ~K~, with the whole part tracked by another global variable since it applies to all numbers equally. Looking at the first ~K~ numbers, an operation of type 2 moves a total of ~X~ numbers (where ~X~ is the remainder modulo ~K~) to the following section. We also know exactly which ~X~ numbers are moved. From the general form of rotation, we can see that it applies to the last ~X~ numbers of the sequence: ~B, B+1, \dots, K-1, 0, 1, \dots, B-1~. Since these numbers are always contiguous, we can increase the interval in time ~\mathcal O(1)~. In the array tracking the sections for each of the ~K~ numbers, we add a ~1~ to the beginning and a ~-1~ to the end of the interval.

The positions of the first ~K~ numbers are thus obtained from two parts. One defines the section that each number is in, and the other defines the position inside the section. After obtaining the positions of the first ~K~ numbers, the positions of the remaining ~N-K~ numbers are derived as described above.

Since each operation is now processed in time ~\mathcal O(1)~, the total complexity is ~\mathcal O(N+Q)~.