Mr. B is an English teacher at Pierre Elliott Trudeau High School. He is infamous for his "questionable" teaching practices – particularly the way he marks. Sometimes, he marks assignments solely based on student favoritism. Other times, he gives his students' assignments to other teachers to mark. He might even randomly generate his students' marks!
For an upcoming essay about microwaves, which you have to finish over Christmas Holiday, your teacher Mr. B has decided to use an advanced method of marking. He will transform each essay into a hash value and determine its mark using the hash value.
Mr. B's hashing algorithm works as follows:
- The hash value is a non-negative integer.
- The hash value is initially .
- For each lowercase English letter, multiply the hash value by a seed value, , add the letter's value to the hash value, and mod the hash value by a mod value, .
The final mark of the essay is the final hash value (the highest possible mark is ).
However, Mr. B has given you some constraints to the essay. The essay must contain exactly space-separated strings, all unique, only composed using lowercase English letters.
Fortunately, a friend of yours has managed to find out the seed value, , and the mod value, , of Mr. B's hashing algorithm. All you have to do now is write the essay. Can you write an essay that will earn you a mark of ?
Constraints
and are coprime. That is, , where denotes the greatest common divisor of and .
Subtask | Points | |||
---|---|---|---|---|
1 | 5 | |||
2 | 5 | None | ||
3 | 10 | None | ||
4 | 15 | |||
5 | 20 | |||
6 | 20 | For , | ||
7 | 25 | For , |
Warning: If the size of your output is greater than 8 MB, you will receive an Output Limit Exceeded
verdict.
Input Specification
The only line of input will contain four space-separated integers: , , , and .
Output Specification
Output, on a single line, an essay that will receive a mark of . It is guaranteed that such an essay exists.
Sample Input
5 172 31 307
Sample Output
english is the worst subject
Explanation for Sample Output
The hash value initially starts at .
After processing the first letter, e
, the hash value becomes .
After processing the second letter, n
, the hash value becomes .
The final hash value, and thus the mark of the essay, is .
Comments
spaces don't count in the hashing algorithm right?
Spaces are not put into the hash. However, spaces count towards the 8 MB limit.