Sitting and Standing

There are N students, numbered from 1 to N from left to right. Each student is either standing (u) or sitting (d). The given arrangement is called step 0.

When moving from one step to the next, all students update their states at the same time. A student changes state if the student immediately to their right was standing in the current step. If the student immediately to their right was sitting, the student keeps the same state. For student N, the student to the right is student 1.

Given the step 0 arrangement, determine the arrangement after M steps.

The first line contains two integers N and M (1 <= N <= 1,000,000, 1 <= M <= 1,000,000,000).

The second line contains a string of length N with no spaces. Its characters describe the step 0 states of students 1 through N in order. u means standing, and d means sitting.

Print one line containing the students' states after M steps, in the same format as the input string.