Subtask 1

For the first subtask, for each operation, we can iterate through each pair of small turntables and determine if a lamp is on the line segment between them. We can compute the angle of the line segment based on the isosceles triangle formed between the two small turntables and the large turntable. There is a lamp on the line segment if and only if the angle is a multiple of ~\frac{360}{N}~ degrees. We can then print the sum of the polish values of each of these lamps.

Time Complexity: ~\mathcal{O}(Q \cdot N^2)~

Subtask 2

One helpful observation is that when ~N~ is odd, the answer is always ~0~. When ~N~ is even, it is the case that the closest ~\frac{N}{2} - 2~ lamps to the centre contribute to the required sum if ~N~ is a multiple of ~4~ or ~\frac{N}{2}~ if it is not. We can precompute the sum for each of the ~N~ possible rotations of each small turntable. We can also see that rotating the large turntable clockwise is equivalent to rotating each of the smaller turntables counterclockwise. For each operation, we can print the sum of the precomputed sums for each of the smaller turntables' current rotation.

Time Complexity: ~\mathcal{O}(Q \cdot N)~

Subtask 3

For the third subtask, we can split the operations into blocks. Given an initial rotation of each of the smaller turntables, if we can quickly compute the answer for all possible rotations of the large turntable, we can then keep a buffer of all operations on the small turntables and apply the smaller operations one by one after looking up the answer for the current rotation of the large turntable. To compute the answer for all possible rotations of the large turntable, we can observe that there are ~N~ possible rotations of the smaller turntables, with each sum of the polish values of the closest lamps to the centre contributing some number of times (between ~0~ and ~N~) to the answer for each rotation of the large turntable. In fact, if we consider the frequencies of each of the rotations of the smaller turntables, we can treat this as a polynomial of degree ~N - 1~. We can also treat the sum of the polish values of the closest lamps to the centre for each of the smaller rotations as another polynomial of degree ~N - 1~. If we multiply these polynomials together, we can see that it will result in a polynomial of degree ~2 \cdot N - 2~ with the answer for each rotation ~i~ of the large turntable being the sum of all coefficients ~c_j~ where ~j \equiv i \bmod N~. We can multiply these polynomials quickly in ~\mathcal{O}(N \log N)~ time, which means that the optimal size of the blocks of operations is approximately ~\sqrt{Q \log N}~.

Time Complexity: ~\mathcal{O}((N + Q) \cdot \sqrt{Q \log N})~