Going Round in Circles

Let’s take a binary string: 1101001. After the first cyclic left shift, it becomes: 1010011 After the second cyclic left shift, it becomes: 0100111 = 100111 After the third cyclic left shift, it becomes: 001111 = 1111 After the fourth cyclic left shift, it becomes: 1111

There’s no change after the third cyclic left shift. In fact, no matter how much cyclic left shift occurs here, the integer will not change.

It is easy to see after at most 32 cyclic left shifts an integer won’t change anymore.

So we can keep a segment tree on the numbers, with an extra flag in each node. This flag determines if all the numbers in the array in corresponding range has converged(Meaning it will not change anymore like 1111)
While updating we will descend from a node in segment tree if all the numbers have not converged in the range.

Total complexity: O(maximum bits in $A_i$ in binary representation$\cdot$n$\cdot$logn)