Description

Given a square matrix A and a smaller square matrix B inside A, print the location of B.
For example, if A is
1 2 3 4
5 6 7 8
8 7 6 5
4 3 2 1

and B is
7 8
6 5
, then the answer is 
1 2

because B is in row 1 and column 2 in A.

Input

The first line contains two integers m and n, which are the sizes of A and B. (m and n <=20)
The following m lines contain the m rows of elements of A (each row has m integers).
The next n lines contain the n rows of elements of B (each row has n integers).

Output

The output is a line that contains two integers indicating the location of B in A.
The first integer is the row index and the second integer is the column index. The two integers are separated by a whitespace and there is a '\n' at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ugandan Knuckles is trapped in a dungeon. He wants to find his queen. He finds a stele (碑) that there are n strings on it. You can move the strings in any order you want.

The way to go out is that for each string, all strings placed before it are its substrings.

For example:

If the stele contains strings:

"n"

"ugandan"

"ganda"

"gan"

You should arrange the strings into the order:

"n"

"gan"

"ganda"

"ugandan"

Help Knuckles get out of the dungeon or he will spit on you.

Input

Input contains several lines.

First line contains only one integer n (1<= n <= 1000)

Following n lines, each line contains one string s ( 1<= length of s <= 1000 )

The string s only contains lowercase English letters.

Output

If it's impossible to arrange the strings in the desired order, print "NO".

If it's possible, print "YES" .

And then print n lines each line contains one string in required order.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recently, scientists finally find a way to produce unlimited energy. The scientists call it "Cat-Toast".

In case that someone might not know:
While buttered toast falls onto the ground, it will always land with its buttered side - Falling Toast Theorem(FTT)
While cats fall onto the ground, they will always land with their four feets. - Falling Cat Theorem(FCT)
By FTT, we can assume that if we put butter on both sides of the toast, we might create a perpetual motion machine, because by FTT, we know that the buttered side will land onto the ground. However, there are two buttered sides. If any side of the toast lands, there will be a contradiction, so the toast will never fall and continue spinning around. We can apply the same way on FCT.
However, there is a big problem. if we just put two buttered toasts or two cats together, there will be no momentum, and obviously it won't spin except for any external force, which cannot be a perpetual motion machine. This problem had confused scientists for centuries.
Recently, scientists finally got a breakthrough progress. They combined a cat and a buttered toast and it just spins by itself! Due to the difference mass of a cat and a buttered toast, the machine itself will provide the momentum to spin, and it will never fall onto the ground (due to the contradiction we proved before), the first perpetual motion machine was born!

The original video is here.

Scientists found that if two cat-toasts' distance are equal to or closer than r, there will be a collision which cause a small black hole and soon disappear, which is very dangerous. The cat-toast must be secured separately. Also, if there are multiple cat-toasts that will collide, those cat-toasts will all collide together and spawn exactly one black hole. If there's any problem, you may refer to Sample I/O.
One day in NTHU, a servitor just carries a lot of cat-toasts, each with a secured box. He accidently falls down and all the cat-toasts just drop out of their own boxes.
Now given r and all the coordinates of all cat-toasts, the servitor wants to know how many cat-toasts remains there after some destructive collisions and how many black holes spawned. 

Note that the distance of two cat-toasts is sqrt( (x1-x2)^2 + (y1-y2)^2 ), where (x1,y1) and (x2,y2) are the coordinates of this two.

Input

The first line contains two integers n, r, indicate the number of cat-toast, the distance r decribed above.
The next n lines, each line contains two integers x_i, y_i, indicates the location of the i-th cat-toast.
1 <= n <= 1000, 1 <= r <= 10⁴
1 <= x_i, y_i <= 10⁴

Output

The first line of the output is the total number of cat-toasts that still remains and the total number of black holes after collisions, separated by a space.
Remember to output a '\n' at the end of the output.
(In fact, expect for the problem DO ask you not to output a '\n' at the end of the output, mostly you shoul output a '\n' at the end.)

Take Sample I/O as an example, obviously cat-toast located at (5,15) and (1,15) will collide. (1,7), (1,3), and (5,3) will collide together because (1,7), (1,3) collides, and (1,3), (5,3) collides, just like a chain, or a tree.

There's only one remaining cat-toast located at (500,500) and spawned 2 black holes, so the answer is "1 2" without quotes.

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

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas is a shopaholic.

There are n different kinds of items in a store and Osas wants to buy every kinds 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 kinds of 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.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This is a bonus problem. You can get 2 total points at most if you solve this problem.

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