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

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas is a shopaholic.

There are n different items in a store and Osas wants to buy every of them.

The i-th item cost a_i dollars, but the price fluctuates greatly recently.

Tomorrow the i-th item's price will be b_i dollars. Osas has an special ability that he can know the price tomorrow.

Because he's a shopaholic, he wants to buy every items in at most two days. Osas must buy at least k item at first day, or he will be crazy.

Help Osas find out the minimum money he should pay to buy every kinds of item in the shop.

Input

Input contains third lines.

First line contains two integer n ( 1 <= n <= 10⁵ ) and k ( 0 <= k <= n ).

Second line contains n integer a₁ ~ a_n ( 1 <= a_i <= 10⁵).

Third line contains n integer b₁ ~ b_n ( 1 <= b_i <= 10⁵ ).

Output

Output only contains one integer -- the minimum price Osas needs to pay.

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

After rain comes sunshine and rainbow.

5/17 is the International Day Against Homophobia, Transphobia and Biphobia(國際不再恐同日), which is also the day that legislative committees trial the special law about LGBT. They eventually pass a draft that fully in line with the referendum, which make Taiwan be the first Asia country that pass a law for LGBT.

Knuckles is on his way of finding his queen. When he arrived Taiwan and see a lot of rainbow flags, he wondered that these rainbow flags might be a clue of the location of his queen. He will give some operations about these flags, you are going to help him, or he'll spit on you.

• There are colors on these flags. The colors include: "Red", "Orange", "Yellow", "Green", "Blue", "Purple", which are the color of rainbow.

• Knuckles has a sequence of colors. Initially, the sequence is empty.

• Knuckles has several operations: insert, erase1, erase2, reverse, show.

  • insert <color> <dest>: means insert <color> after the location of <dest>. For example, insert Yellow 5 means insert a "Yellow" after the 5-th location. If <dest> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • erase1 <dest>: means erase the color locates at <dest>. For example, erase1 4 will erase the 4-th color in the sequence. If <dest> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • erase2 <color>: means erase all <color> in the sequence. For example, erase2 Purple will erase all the "Purple" in the sequence. After the operation, There should be no "Purple" in the sequence.

  • reverse <dest1> <dest2>: means reverse the elements from <dest1> to <dest2>. If the order was originally {"Yellow", "Purple", "Blue"}, after reversing, the order should become {"Blue", "Purple", "Yellow"}. If <dest1> or <dest2> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • show: show the sequence according to the order.

You are going to implement a linked list that support these operations. We have implemented show operation, what you have to do is to implement the remaining operations: insert, erase1, erase2, reverse.

Input

The first line contains an integer n, indicates the number of operations.

There are n lines below. Each line contains one operations described above.

<color> will only appear the 6 colors described above.

insert: 0 <= <dest> <= 10000

erase1: 1 <= <dest> <= 10000

reverse: 1 <= <dest1>, <dest2> <= 10000

1 <= n <= 5000

Output

When show operation is called, you should output the correct sequence after operating.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Uncle Huang wants to find a tutor. He has n students to choose from. 

Students are indexed 1, 2, . . . , n and standing in a circle. 

Uncle Huang will count every k-th students in clock-wise.  

The k-th student is going to be chosen but the student will disappear(Nobody knows why!) therefore Uncle Huang will continue his counting and start from the next student.

The last remaining student will be his tutor.

Tell Uncle Huang the index of the student who will be his tutor.

example: If n = 5, k = 7

Hint: 約瑟夫斯問題(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)

This problem is partial judge.

Note: k might be very large, if you just count k students you will get TLE. Try to count less by using mod.

Input

The input will end by EOF

Every testcase only contains two integer n(1<= n <= 1000) and k(1 <= k <= 10⁹)

Output

For each testcase print the index of the student who last remaining.

remember to print \n at the end of every output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Uncle Huang wants to find a tutor. He has n students to choose from. 

Students are indexed 1, 2, . . . , n and standing in a circle. 

Uncle Huang will count every k-th students in clock-wise.  

The k-th student is going to be chosen but the student will disappear(Nobody know why!) therefore Uncle Huang will continue his counting and start from the next student.

The last remaining student will be his tutor.

Tell Uncle Huang the index of the student who will be his tutor.

example: If n = 5, k = 7

Hint: 約瑟夫斯問題(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)

Note:

This is the hard version, if you use link list to solve this problem you will get TLE.

If you use recursion to solve this problem you will get MLE for the testcase 6.

The idea for solving this problem: 

If we already know the position that will be the last remaining for n = m-1( if n==1 then the answer is obvious. The answer will be 1 ), can we use this clue to calculate the answer for n = m?

Input

The input will end by EOF

Every testcase only contains two integer n(1<= n <= 10⁷) and k(1 <= k <= 10⁹)

Output

For every testcase print the index of the student who last remaining.

remember to print \n at the end of every output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

No description, literally. I'm tired.

_(:3∠」)_

• You have a sequence a. Initially, a has exactly one integer. You're at the place of the 1st element.

• There are some operations below:

  • insert <val1> <val2>: insert <val2> number of elements, all with value <val1>. Insert them next to your position.

  • erase <val>: erase <val> number of elements next to you.

  • move <value>: Move <value> number of indexes forward. Note that <value> might be negative, which means you might move forward or backward.

  • show: Start from your position, output the sequence a. Each element separated by a space. Note that there should be no space at the end but a '\n'.

For example: a = {2}, and execute operations below:

• insert 3 6 // a = {2,3,3,3,3,3,3}, you're at the 1st position.

• insert 1 1 // a = {2,1,3,3,3,3,3,3}, you're at the 1st position.

• erase 2 // a = {2,3,3,3,3,3}, you're at the 1st position. Erase 1 and 3.

• move 5 // a = {3,2,3,3,3,3}, you're at the 1st position. Originally was the 6th position.

• erase 3 // a = {3,3,3}, you're at the 1st position. Erase the first 2 and two 3.

• show // print 3 3 3. Note that there should be a '\n' at the end.

Input

The first line contains an integer x, indicates the first element in a.

The next line contains an integer n, indicates the number of operations.

There are n lines below. Each line contains exactly one operation.

1 <= n <= 3000. All numbers in a are in int range. We guaranteed that there must be at least 1 element in a, and the number of insert and erase elements won't exceed 3000.

Also, the total elements of a won't exceed 3000.

Output

Output the correct a if there's show operation.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It's a beautiful day outside. birds are singing, flowers are blooming... on days like these, kids like you... Should be burning in hell. Uhhhh... I mean, nothing, literally. (original: undertale sans dialogue)

Even such a beautiful day like this, we shall watch out for the chance that there might be bombing plane bombing our campus. That's why we need our fortification, that is, the well-known "Airplane Shooter".

"The True Appearance of the Airplane Shooter" PC by TA

However, living in this "peaceful" era, we don't actually need to worry about bombing planes or "Little Boy" or somethin else like that. The Airplane Shooter is no longer be needed, so the school committee decided to turn it to a "public art", everyone is able to get closer to our legendary Airplane Shooter.

Nothing lasts forever. Some "fart child" use it to flash those unfortunate passers. The famous Airplane Shooter has also become the infamous "Moto-shooter".

Now, Knuckles is going to shoot(flash) those goddamnpoor motorcycles down because those motorcycles block his way of finding his queen.

Knuckles could recognize the owner of every motorcycle. He prefers to shoot those school administration staffs first, especially the president. If their administration level are the same, he would like to shoot those motorcycles with smaller license plate number(which is literally a "number").

Given the sequence of those motorcycles and their infos, you are going to tell Knuckles the order of shooting down.

• Given a sequence a. The elements of a has the following infomations:

  • index: The index is followed by the input order, starts from 1. The input won't contain index, you have to record it yourself. Smaller input index has higher priority.

  • admin level: Level starts from 0 to 999. level 0 has the highest priority, while level 999 has the lowest.

    • level 0: president Hong Hocheng
    • level 1: stuff of different school affairs
    • level 2: junior sister(學妹)
    • level 3: senior sister(學姊)
    • level 4: senior brother(學長)
    • level 5: campus stray dogs/cats
    • level 6: squirrel
    • level 7: pigeon
    • ......
    • level 999: junior brother(學弟)

  • license number: An integer. Smaller number has higher priority.

• You are going to sort a. Element with higher priority brings to the front. Compare admin level first, then license number, then index.

• Output index(the old one) of every element in the new a.

Input

The first line contains an integer n, indicates the number of elements in a.

There are n lines below. Start from the first line of the n lines, the i-th line contains the i-th information. Each line contains 2 integers admin level and license number.

1 <= n <= 10⁵, 0 <= admin level <= 999, 1 <= license number <= 10⁹

Output

Output the old index of every element in the new a respectively, each separated with a space

Note that there should be no space after the last number but a '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss