Problem A
Advice
Gabriel Bruce’s lifelong dream is to become a professional baseball pitcher. Gabe, as he is known to his friends, started practicing by throwing ping pong balls and eventually worked his way up to cantaloupes. This led his family to think that he was a picky eater, so they boiled his cantaloupes from then on.
Eventually, Gabe Bruce was accepted onto a team consisting entirely of pitchers, the Anti-Cantaloupe Pitching Collective. The team is utterly hopeless, what with their complete inability to run or bat, and what’s worse, they despise cantaloupes! Tragically, Gabe has had to hide his friendship with Mr. Booth, the talking boiled cantaloupe (actually, Gabe is on a first-name basis with him, so he calls him Abe). This is a shame, since Abe Booth is full of valuable wisdom about everything baseball-related.
For instance, just the other day, Mr. Booth said ‘ACPC’. At first glance, you might think that this is exactly the type of thing a boiled cantaloupe would say, but upon closer inspection, it contains a hidden message. Define $f$ to be a function which takes a nonempty string of uppercase letters and produces a nonempty string of uppercase letters as follows: First the sum of the letters is calculated, where for the purposes of this sum ‘A’ is $1,$ ‘B’ is $2,$ ‘C’ is $3,$ …, ‘Z’ is $26.$ Then, we take the sum modulo $m,$ where $m$ is a fixed positive integer agreed upon by Gabe and Abe, equal to the ideal number of seconds that a cantaloupe of Mr. Booth’s weight and size should be boiled, and then take the result modulo the length of the string, and remove that many letters from the beginning of the string. Finally, each letter is replaced by the letter which comes after it in alphabetical order, except for ‘Z’, which is replaced by ‘A’. Now consider applying $f$ to ‘ACPC’ with $m = 7.$ Since ‘A’, ‘C’ and ‘P’ respectively map to $1,$ $3$ and $16,$ the sum of ‘ACPC’ is $1 + 3 + 16 + 3 = 23.$ Modding this by an $m$ value of $7$ gets us $2,$ and modding $2$ by $4,$ the length of the string, also gives $2,$ meaning the first $2$ characters are removed to form ‘PC’. Finally, doing the letter replacement, we get ‘QD’. Of course! An invaluable piece of pitching advice!
Not only does applying $f$ to the wisdom of Mr. Booth yield excellent tips for baseball improvement, Gabe has discovered that $f$ can be applied multiple times for even better results. Continuing our previous example, suppose that $f$ is applied to ‘QD’, still with the fixed value of $m = 7.$ The letter sum is $17 + 4 = 21,$ modding this by $m$ gets us $0,$ and modding this by $2,$ the length of ‘QD’, also gets us $0.$ Therefore, no letters are removed, and after the letter replacement, the result is ‘RE’.
Now, Gabe has hidden his cantaloupe companion in his pocket and all he needs is a program that can apply $f$ to the sayings of Mr. Booth one or more times. That way, he can get the program implanted inside him and become a cyborg who is too swole to control.
Input
The first line of input contains three space-separated positive integers, $n,$ $t$ and $m,$ each of which will be no more than $10^5.$ The second and final line contains a string $S$ of $n$ uppercase letters.
Output
Output the string obtained by successively applying $f$ to $S$ for $t$ times, using the provided value of $m$ for each function application.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 7 ACPC |
QD |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 7 ACPC |
RE |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 3 17 THROWTHEBALL |
O |
| Sample Input 4 | Sample Output 4 |
|---|---|
5 9 16 TYVRK |
CHEAT |
| Sample Input 5 | Sample Output 5 |
|---|---|
4 3 11 PORK |
RUN |
