Description

There're different kinds of Knuckles in this world. According to the research, there're 26 different kinds of Knuckles.

---

Let's denote different kind of Knuckles as 'a' ~ 'z'.

Knuckles is a magic creature.

If you have at least 2 same kind of Knuckles, you can transform these Knuckles into any kind of Knuckles with same number of them.

For example：

if you have n=3 Knuckles representing as "aab" you can transform 'a' Knuckles into 'b' Knuckles. In the end you will get "bbb" Knuckles.

Because you're a deadly Ethnic nationalism, you want all Knuckles to be the same.

You can do the transformation many times.

Find out whether you can do that.

NOTE: Case 6 limits the memory to 1 MB, so try not to declare a large array.

Input

Input contains two lines.

First line contains only one integer n( 1 <= n <= 10⁷ ), representing the number of Knuckles.

Second line contains one string, the length of n.

 

Output

If you can make all Knuckles the same, output "I'm the god of Knuckles!"

Otherwise,  output "Different makes perfect"

Remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Wow! Look at that youbike! It's so fasion...."

"Hey! Look! Is he.... is he the famous "The king on Akina Mount"(秋名山車神)...? The one who dominates all youbikers on Akina Mount? No way!"

-----------------------------------------------------------

The world's largest youbike racing contest is holding in NTHU. All the best youbike racers come to this place, including "The king on Akina Mount" !!! But now, he has several problems to solve......

Due to youbikes cannot afford really high speed for too long since the components might break and racers would be in danger, so the race commitee sets up several checkpoints along the contest track. Every racer can choose to change a totally new youbike and go, or just pass the checkpoint without changing a new one.

For The king on Akina Mount (we'll just call him "the king" in convenience), his speed is the fastest without any doubt. However, his youbike might break, too. But changing another youbike also takes time, we call it "penalty". The king wants to minimize the penalty, so that he could win this race. He ask you, the legendary mechanic, for help!

---

• The youbike race begins at position 0, ends at the endpoint. 
• While arriving each checkpoint, you can choose either to change a new youbike or continue with the original one. 
• Each youbike has the same damage degree k, and the damage degree will decrease 1 every 1 distance. Changing a new one means reset the damage degree to k. When the damage degree is lower than 0, the youobike breaks and the king loses. 
• Initially, the king is at position 0, and he's riding a totally new youbike, which means the damage degree is initially k.
• Given the position of every checkpoint and the location of endpoint, your task is to find out the minimum number of changing a new youbike. If he cannot reach the end, just output "The Legend Falls."

 

 

Sweet caution:

Do not break the speed when riding youbike.

Input

The first line contains two positive integers, n, k.

The second line contains n positive integers indicate the position of every checkpoint. The position has been sorted in ascending order. The last station indicates the endpoint.

The track is a straight line, and every checkpoint is on the right side of the initial position "0".

1<= n, k <= 100000, the distance between every consecutive checkpoints will not exceed 100000.

0 <= the position of checkpoints <= 2^31-1.

Output

Output the minimum penalty, or "The Legend Falls." if the king cannot reach the end.

 

Take the sample IO as an example, a new youbike can ride at most 5 unit long. The king will change another youbike at stations locate at 4 and 9, and finally reach the end point(14). 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I worked at McDonald. My principle of selling fries is:

"ガンニニ_ヤサイバウ ( gan ni nya sai bau )"

Yeah... "ガンニニ_ヤサイバウ". I don't care if deficit of McDonald occurs or not. The fries sold each time are extremely large. Small size to large size, medium size to giant size, large size to another free one, just like give all the fries in the French fries station away.

I still remember, that month, I worked 25 days. The manager came to ask me, they got 26 boxes of French fries of deficit, do you have any clue?

How the hell could I know.

── Unknown McDonald's ex-employee

Every time that employee thinks of that, he/she always wonders why couldn't he/she stuff more fries, which makes him/her feel bad. 

The employee finds an old record about importing fries each day. The amount of the imported fries increases day by day. 

The employee wonders that whether he/she could left shift the record by a number, and he/she could stuff more and more fries in the first few days. What about the last few days? Who cares. 

The employee couldn't wait to imagine how happy he/she would be if getting the chance! He/She would stuff all the fries out! ​The employee will give you some numbers and ask you how he/she could stuff this much fries.

---

• You are given a non-decreasing sequence named a and a number k. 
• The sequence will left shift (左移) k slots and the first k elements will shift to the end of the sequence. For example: a={1,3,6,8,9}, k=2. After left shifting, new a will be {6,8,9,1,3}.
• Each query has one number f, and you're going to find out the index i such that f <= a_i and |f - a_i| is the smallest. If there's no such i, output "gan ni nya sai bau". If there are multiple i you could pick, choose the i with the smallest index. Note that this is katakana(片假名), not Chinese or something else.

Input

The first line contains three integers n, k, q.

The second line contains n integers, which indicate the elements of sequence a.

There are q lines below. Each line contains one integer f.

1 <= n, q <= 10⁶, 1 <= a_i, f <= 10¹⁵, 0 <= k < n.

Output

For each query, output the index i that f <= a_i and | f - a_i| is the smallest. If there are multiple answers i being the smallest, choose the i with smallest index. If there's no such i, output "gan ni nya sai bau".

Remember to output a '\n' at the end of the output. 

Sample Input  Download

Sample Output  Download

Tags

Discuss