x3JiaYin the Mercedes is issued a challenge from the Black Mage, to fight one to one in an epic battle. x3JiaYin wants to accept the challenge, in hope to destroy the Black Mage one and for all, for the good and safety of the Maple World.
The Black Mage is known to be a recurring evil entity which is known to cause mass events related to other classes. In the past, before Victoria Island and Ossyria were separated, the Black Mage placed a curse on Ellin Forest (Ellinia in present day), so it would slowly be poisoned. This is why Perion exists. Furthermore, he also took control of Zakum and Horntail, making them a lot stronger and fiercer.
According to the Aran's lore, the Black Mage was successfully defeated and sealed away by the five Heroes of MapleStory. However, right before his death, the Black Mage put a curse on the Heroes (all except for Freud, who sacrificed himself to protect Afrien and the Dragon Egg), encasing them in ice for many years. In present day, the Heroes slowly start to thaw and rise once more. One such Hero is the Mercedes.
Edelstein is the place where the Black Mage was raised, and went to Magatia to study alchemy. The Black Wings used Edelstein as a base to resurrect the Black Mage, and took over the city. That made the people of Edelstein live in fear. However, in the darkness lies a small light of hope. That light, is the Resistance!
The Black Mage altered the entire Victora Island, causing cataclysm and chaotic change. The Explorers, the Cygnus Knights, the Heroes, and the Resistance are needed to battle against the Black Mage.
The Black Mage was also responsible for cursing Mercedes and her hometown, Elluel, encasing all the elves and herself, in ice. He betrayed the Demon Slayer as well, breaking his promise on not laying a finger on the Demon Slayer's family, in which the Black Mage ordered his hometown destroyed. The Demon Slayer discovers his master's betrayal and turns against him.
When it was confirmed the Black Mage would rise, the Explorers, Cygnus Knights, Heroes, and Resistance forms a mass alliance to stand ready for battle.
In x3JiaYin's mission to bring the Maple World to safety, she has to pass several challenges posed by the Black Mage. One of which was a jump quest. However, this jump quest has a time limit and failing to meet the time limit would result in her capture.
In order to complete this jump quest, she has to jump on N different pillars, labelled from 1 to N. Her goal was to jump from pillar 1 to pillar N using all or a subset of the pillars. She is not restricted to utilize the pillars in any order. Each pillar has a specific height, with the ith pillar having height Hi. However, Black Mage has planted serveral Zakums and Horntails between those pillars, making jumping from one pillar to another almost impossible.
However, Grendel the Really Old, the Magician Job Instructor has identified a weakness in the Black Mage's formation. He realised that it IS possible to jump from 1 pillar to another, as long as the difference between their heights, when divided by M, leaves a remainder of R and they are not of the same height. However, to utilize this weakness, the time required to jump between these pillars would be their difference squared, in seconds. Grendel also mentions that the maximum time x3JiaYin needs to complete the challenge is always less than 231 - 1 seconds as x3JiaYin would die after that long anyway. Being so wise, he would not have told x3JiaYin about the weakness in the first place.
Now, the question is: Should x3JiaYin accept the challenge posed by the Black Mage? To figure this out, she needs to know whether it is possible for her to complete the jump quest safely, and if so, how long would she take?
The first line of input has 3 integers, N followed by M and then R
Subsequent N lines consists of Hi, with the ith line having Hi.
A single integer, which indicates the time taken for x3JiaYin to finish the jump quest.
If it is not possible for x3JiaYin to finish the jump quest, output
Black Mage you scammer!!!
0 < N ≤ 100000
0 ≤ Hi ≤ 10000
1 ≤ M ≤ 1000
0 ≤ R < M
- Subtask 1 (20%): 0 < N ≤ 100
- Subtask 2 (30%): 0 < N ≤ 1000
- Subtask 3 (50%): 0 < N ≤ 100000 & M ≥ 100
Sample Input 1
5 10 3
Sample Output 1
Sample Input 2
5 10 4
Sample Outpue 2
Black Mage you scammer!!!