URI Online Judge | 1622

Lamps

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

In your last school work, you developed a project somewhat curious. It's about N lamps arranged one beside the other, enumerated from 1 to N from the left to the right, and a single switch. When this switch is pressed, he changes the state of one of the lamps (if it was on, it turns off, and vice versa).

The differential of your project is the behavior of this switch. Instead of changing the state of a particular lamp, it intercalates between the lamps in which it will operate, working in the following way: in the first time it's pressed, the switch changes the state of the lamp number 1; in the second, and the next times, it changes the state of the lamp that is K positions to the right from the last lamp. If it comes to the end of the sequence, it continues to count from position 1.

For example, be N = 8 and K = 3, if we press the switch 4 times it will change the lamps 1, 4, 7 and 2, respectively.

You became intrigued with your own project, and decided to make a few tests. Given the initial state of the N lamps (on or off), the value of K and a number M of times in which the switch was pressed, say the final state of the N lamps.

Input

There will be several test cases. Each test case starts with two integers N and Q (3 ≤ N ≤ 100, 1 ≤ Q ≤ 1000), representing the number of lamps and the number of queries, respectively.

Following there will be a line with N characters, representing the state of the N lamps. The i -th character indicates the state of the i-th lamp, being it on (character “o”) or off (character “x”), for all 1 ≤ iN.

Following there will be Q lines, each with two integers K and M (1 ≤ K < N, 1 ≤ M ≤ 10⁶), indicating the size of the “jump” that the switch gives (as said in the problem description), and the number of times it was pressed, respectively. At each query the switch starts at position 1.

The last test case is indicated when N = Q = 0, which shouldn't be processed.

Output

For each query print one line, containing N characters each, where the i-th character indicates the state of the i-th lamp, being it on (character “o”) or off (character “x”).

Sample Input Sample Output

8 3
xxxxxxxx
3 3
3 4
3 7
11 3
xooxoxxxxox
5 6
10 43
9 1000
0 0

oxxoxxox
ooxoxxox
oooooxoo
ooooxoxxxxo
xxoxoxxxxox
oxooxooooxo