Subtask 1

The only numbers needed are ~1~ and ~2~. For every operation with ~Z_i=2~, fill ~A_{X_i},A_{X_i+1},\dots,A_{Y_i}~ with ~2~. After all the operations, check if the GCDs are correct.

Time Complexity: ~\mathcal{O}(NM)~

Subtask 2

Consider a single requirement ~X_i,Y_i,Z_i~, we can reframe this requirement as the following two restrictions:

1. Every single number from index ~X_i~ to ~Y_i~ to be divisible to ~Z_i~
2. The GCD of the subarray ~A_{X_i},A_{X_i+1},\dots,A_{Y_i}~ is minimized

For any index ~i~, to make sure it satisfies the first restriction of all requirements that pass over it, it must be some multiple of the LCM of all ~Z~ of those requirements. Additionally, as we also want to minimize the GCD of the subarray specified in each requirement (while also satisfying the divisibility restriction), it's always optimal to take the LCM.

Thus, for each value in our final array, we collect all the requirements that pass over it, and just set it to the LCM of the ~Z~ values of those requirements. Then, we just check that our answer is valid by making sure the GCD restriction on each requirement is satisfied.

Time Complexity: ~\mathcal{O}(NM)~

Subtask 3

There are many ways to optimize the subtask ~2~ solution for full points, but this solution will not involve any data structures beyond difference array because throwing segment trees at the problem is boring.

To compute which requirements pass over any given index, notice that ~1 \le Z_i \le 16~, so we can just use ~16~ difference arrays to keep track of which requirements pass over any given index.

Checking that the GCD restriction of each requirement is satisfied is a bit more complicated. In this case, we'll treat them as range GCD queries on our final array and we first group the queries by their right endpoint. We then process them offline in increasing order of right endpoint. At each right endpoint from ~1, 2, \dots, N~, we consider the GCD of all subarrays that end at that endpoint, and observe that as we move from the shortest to longest subarray, the GCD will change at most ~\log(lcm(1, 2, \dots, 16))~ times. Thus, we can just maintain these GCD changes with a vector and answer all queries ending at that right endpoint with binary search.

Time Complexity: ~\mathcal{O}(N \max(Z_i) + (N+M) \log(\max(A_i)))~