Subtask 1

Due to the cyclic nature of the algorithm, it suffices to simulate the algorithm until we encounter the 0 at the front of the string, at which point it can be removed and the remaining characters outputted in order.

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

Subtask 2

If ~M = 2~, note that we care only about the 0 that is removed last. This can be done by comparing ~a_i~ values, breaking ties by comparing the indices at which the 0's appear in the input string. We can then remove the 0 that is removed first without any consequence.

From this point onwards, we can perform the same sort of simulation as outlined in Subtask 1.

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

Subtask 3

We still only care about the last 0 that is removed. We can find the index of this 0 by sorting the 0's based on their ~a_i~ value and breaking ties by selecting the 0 that is further back. Let's call the index of this last 0 ~i~. We now separate the number into two strings ~A~ and ~B~, where ~A~ contains all non-0 characters in the input order before ~i~, and ~B~ contains all the non-0 characters in the input order after ~i~. When we reach ~i~ for the last time, the string can be shown to be ~B + A~, where ~+~ represents concatenation.

A slightly faster solution involves maintaining ~i~ by iterating through the string instead of sorting.

Time Complexity: ~\mathcal{O}(N \log N)~ or ~\mathcal{O}(N)~