George is a student with an absurd memory. Recently he created a way to show his abilities, using N complete decks of cards.
First, the N decks are put on a line, and are numbered from 0 to N - 1. At first each deck is ordered in the usual way, first by suit (Spade, Heart, Club and then Diamond) and the by figures (ace, two, three, ..., ten, jack, queen and king). Cards in each deck are numbered from 0 to 51, from bottom to top, being 0 the Ace of Spades, 15 the three of Hearts, and 51 the King of Diamond.
To show his abilities, George, blindfolded, plans to ask a volunteer from the crowd to do some of the following queries:
- Shuffle: The volunteer announces 4 integers A, B, I and J and then swaps the card I with card J from all decks numbered from A to B.
- Sum: The volunteer announces two integers A and B, computes the sum of the figures of the top cards (with number 51) from all decks numbered from A to B, writes the result on a piece of paper and shows the crowd.
The volunteer will make some sequence of those queries and, to show his abilities, after each Sum query, George will announce the result to the crowd and they will check if it matches the one computed by the volunteer.
As George wants to practice before doing the show to a real crowd, he wants you to write a program that, given a sequence of Shuffle and Sum queries, print the result of each Sum query.
The first line has a single integer T, the number of test cases.
The first line of each test case has two integers N and Q, the number of decks and the number of queries. Each of the next Q lines contains a query, it begins with 0 for a Shuffle query, followed by four integers A, B, I and J; or 1 for a Sum query, followed by two integers A and B.
Limits
- 1 ≤ T ≤ 103
- 1 ≤ T·N ≤ 5·104
- 1 ≤ T·Q ≤ 5·104
- There is at least one Sum query per testcase
- 0 ≤ A ≤ B < N
- 0 ≤ I, J < 52 and I ≠ J
For each Sum query, print the answer in a single line.
2
10 6
1 0 9
1 5 5
0 0 4 51 0
1 0 9
0 5 9 51 1
1 0 9
8 3
0 2 3 51 48
0 0 5 51 49
1 1 3
130
13
70
15
33
Every two years the conference "Random Structures and Algorithms" takes place. It brings together the main researchers on the area. It's a tradition to do the "Random Run" (see http://rsa2011.amu.edu.pl/run.php for the 15th edition of the event) a race in which initially a dice is rolled to decide the number of laps that must be ran on the track. The competitors run and when they finish this number of laps they must roll the dice again and run the rolled number of laps to finish the race.
The 16th conference is planned to take place in Poland in 2013, near the date for the ICPC World Final. This year the organizers plan to do something more... cultures, while still preserving the random and fun aspect of the event. N bars will be chosen in the city of Warsaw (internationally know for its lively bars and first class beer). Initially the organization creates a network between these bars, defining that two bars are neighbors if they share some characteristic (having the best beers, the best atmosphere, the friendliest staff, etc).
The competitors start the race in some bar X, and can continue in the same bar or go to some of its neighbors. If the bar X has D neighbors, the probability that the competitor will go to each of X's neighbors is 
, and they also have chance to stay in bar X. The winner is the participant that returns to his start bar first. Notice that the winner may not walk at all! The organizers expect this to be a great event, but are worried that it may take too long for a competitor to return to his or her start bar.
They asked you to create a program that determines the expected number of visits to bars a competitor will do before he finishes the race. Repetitions must be counted. For example, if a competitor started the race in bar X, change to bar Y, stayed in bar Y, and then returned to bar X, then the number of visits was 3, because we do not count the initial stay in bar X, only the return.
The first line has two integers N and M, the number of bars and the number of neighbor relations. Then follows M lines, each with two distinct integers A and B, meaning bar A and B are neighbors. The bars are numbered from 1 to N.
Limits
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 5·105
- 1 ≤ A, B ≤ N
Print N lines, each one containing two integers Ai and Bi, meaning the expected value for a competitor starting in the bar i is 
. Ai and Bi must be coprimes.
2 1
1 2
2 1
2 1
5 3
1 2
3 4
4 5
2 1
2 1
7 2
7 3
7 2
3 3
1 2
2 3
3 1
3 1
3 1
3 1
Wieliczka city in Poland is known for its imposing salt mine. The extraction of salt must obey important restrictions, since the walls and ceiling must stay stable as the good is being extracted. Engineering studies show that the production of salt of a mine can be modeled by a polinomial A(x) (where x is the total volume extracted from the mine). It is know that after a day of work, when x0 material was extracted from the mine, the production now becomes q(x) and there is a waste of r where A(x) = q(x)(x - x0) + r.
Your task id, given A(x) and an integer x0, determine the waste r and the new polynomial related to the new production capacity q(x).
The first line has an integer T, the number of test cases.
Each test case begins with two integers n and x0, the number of terms in the polynomial and the quantity of extracted salt. The following line has n + 1 integers, the coefficients of A(x). The ith integer on the line is the coefficient of xi - 1.
Limits
- 1 ≤ T ≤ 104
- 1 ≤ n ≤ 15
- 1 ≤ x0 ≤ 50
- Each coefficient is between 0 and 100
For each test, print the waste r and then a line with n integers, the polynomial q(x). The ith integer in that line is the coefficient of xi - 1 in q(x). It is guaranteed all terms in the output will fit in a 64-bit signed integer.
3
2 3
3 2 4
3 7
1 10 5 7
1 30
1 0
45
14 4
2717
388 54 7
1
0
In current days a fire flower is not considered a strange thing, since they are famous in some well-known games. In Poland mythology however, fire flowers are mystical flowers of great power, kept by evil spirits. They had this name because they were so bright that it was impossible to look directly into them. Whoever had such flowers was granted the ability to read minds, find hidden treasures and expel evil.
To obtain a fire flower, a person needed to look for it in a forest at midnight, on the eve of Noc Kupały. It bloomed exactly on midnight, and to harvest it, one should draw a circle around it. It may seem an easy task, but the evil spirits tried to distract anyone trying to harvest the flower, and anyone that failed to draw the circle died.
Given two circles, one drawn by the adventures and the other representing the flower, your task is to decide whether the adventurer died or lived to tell the tale and became rich.
The first line has an integer T, the number of test cases.
Each test case is composed of 6 integers in a single line, R1, X1, Y1, R2, X2 and Y2. The circle drawn by the adventurer has radius R1 and center (X1, Y1). The circle that represents the flower has radius R2 and center (X2, Y2).
Limits
- 1 ≤ T ≤ 103
- 1 ≤ R1, R2 ≤ 103
- |X1|, |Y1|, |X2|, |Y2| ≤ 103
For each case print Dead if the adventurer died, or Rich otherwise.
4
6 -8 2 3 0 0
7 3 4 2 4 5
3 0 0 4 0 0
5 4 7 1 8 7
Dead
Rich
Dead
Rich
The Malbork castle is the largest brick castle in the world. It was built in 1274 in honor to Holy Mary, and is located near the river Nogat, in Poland. During World War II it was totally destroyed. In this times it was discovered that the castle was actually built in many phases, and it was surrounded by a fortress and a wall centuries after it had began building.
In those times wall building was a very elaborate task. War tactics showed that it was convenient to build niches in the walls, that is, a recess on them. In these niches a soldier could stand in relative safety, since he could see all the area determined by the line segments in the niche without needing to turn his head (it was considered they field of vision of 180 degrees). The more niches a wall had, the safer the fortress was considered.
Your task in this problem is, given N points, the corners of the fortress, determine how many of them are niches as described above, in which soldiers could stand to protect the castle.
The first line has an integer N, the number of corners of the fortress. Each of the next N lines has two integers Xi and Yi, the coordinates of a fortress corner. The corners are given in clockwise or counterclockwise order. There are no three consecutive colinear points and the wall does not intersect itself.
Limits
- 3 ≤ N ≤ 105
- |X|, |Y| ≤ 1.8·104
Print a single integer, the number of niches in the fortress.
13
0 0
700 100
400 500
1300 600
700 400
1400 200
2200 1200
1500 2000
1500 1700
400 1700
400 2200
0 1900
10 1000
5
3
-32 45
2 19
-100 -3
0
The image shows the first example.
It is becoming more common to use strategies based on social networks for shopping, contract services, arrange meetings, etc. Such strategies often involve interesting mathematical knowledge, like Game Theory. A new trend has appeared, the use of social networks to carry out virtual auctions to contract services. The service providers have agreements between them that enforce a service to cost a predetermine value. The prices a company charges, when it works in collaboration with each of its partners, can be very different, since many factors such as location, previous partnerships, tradition, etc. influence the convenience of a particular partnership.
In this problem you want to estimate the price of a service given by a couple of service providers. It is already known the price of the service given by some companies that have an agreement to work together. Furthermore, if we have two companies A and B, we can contract a service (offered by them) using a chain of companies c1, c2, ... ck, such that
- ci and ci + 1 have an agreement, for i = 1, ..., k - 1,
- c1 = A and ck = B.
Also, we know that the price to contract such chain of companies, is the highest price of a service given by a pair of adjacent companies in that chain. That's the power of social networks!
In the previous figure, despite the fact that the price of the agreement between A and C is 13, the best price (in the network that links these companies) is 9, using the agreements through B.
Your task is to help these virtual auctions. The person interested in contracting a certain service chooses a pair of companies he want to contract, and you need to make a program that answers the minimum possible price of that service.
The first line contains two integers N and M, the number of companies and agreements, respectively. The companies are numbered from 1 to N. Each of the following M lines contains three integers, the ith contains Ai, Bi and Ci, indicating that there is an agreement between companies Ai and Bi whose price is Ci. Each pair of companies has at most one agreement. It is guaranteed it is possible to contract a service between any pair of companies.
The next line contains an integer Q, the number of queries. The following Q lines contain a pair of integers representing the companies which we want to contract.
Limits
- 2 ≤ N ≤ 105
- 1 ≤ M ≤ 2·105
- 1 ≤ Ai ≠ Bi ≤ N
- 1 ≤ Ci ≤ 106
- 1 ≤ Q ≤ 2·105
Print Q integers representing the price of the service for each query.
4 4
1 2 6
1 3 1
2 4 2
3 4 2
2
1 2
1 4
2
2
4 4
1 2 1
2 3 7
2 4 3
3 4 4
4
1 3
1 4
3 2
4 2
4
3
4
3
The dragon of Wawel's hill dwelt a cavern in this hill located in Krakow, Poland. Stories about the existence of this dragon dates back to the 12th century. In 1970 a bronze sculpture was constructed in the place where the dragon may have lived. This sculpture breathes fire from time to time, or when someone sends an SMS with the word "SMOK" (dragon in polish) to the number 7168.
According to legend, King Krak, the founder, promised his daughter's hand in marriage to the who kills the dragon. Several of the bravest knights attempted this without success, and many were killed by the beast. In the search for a brave warrior to solve the problem, the King Krak sent messengers to various polish cities.
The King Krak was a religious person, and believed in the mysticism of the numbers. He wanted his messengers to spread the news to all the villages, but the messengers had to go through exactly K roads between the start and final cites, and no two messengers could take exactly the same path. He did not forbid the messengers to pass through a village or road several times.
After many years of unsuccessful trials, the King Krak himself decided that he would kill the dragon, but was stopped by Skuba, an apprentice shoemaker, that told him that he found a way to kill the beast. Skuba took a fat sheep, killed it and filled with tar and sulfur. This sheep was left during the night (while the dragon was sleeping) in the entrance of the cavern. The next day, in the morning, the city was awakened by a violent explosion: the dragon swallowed the sheep, and had a terrible thirst. After drinking a lot of water from the river, his belly exploded, and pieces of the dragon covered all the city. As promised, the hand of the princess is offered to Skuba, they got married a lived happy forever.
Your task in this problem is, given an integer K, determine how many messengers could be sent from a starting city to the corresponding final city such that all messengers pass walk through exactly K roads, and no two messengers use the exact same path.
The first line has three integers N, M and K, N is the number of cities in the kingdom, M is the number of roads, and K is the number of roads the messengers must go through. Cities are numbered from 1 to N.
The following M lines each describe a road with two distinct integers Ai and Bi, meaning there is a bidirectional road between cities Ai and Bi. There may be more than one road between two cities.
Limits
- 2 ≤ N ≤ 102
- 1 ≤ M ≤ 2·104
- 1 ≤ K ≤ 103
- 1 ≤ Ai, Bi ≤ N
Print N - 1 lines, the ith line should contain N - i integers, the jth integer on the ith line should be the number of messengers when the starting city is i and the final city is i + j. If it is not possible to send any messenger, print - 1, otherwise print the result modulo 109 + 7.
3 2 3
1 2
2 3
2 -1
2
5 13 4
3 2
5 2
1 2
2 4
1 2
2 3
2 3
2 3
3 2
2 1
1 3
2 3
3 2
553 1323 183 183
477 42 42
427 427
60
Warsaw University is one of the most traditional educational institutions in Europe, being almost 200 years old. People like Chopin (musician), Menachen Begin and Itzhak Shamir (prime ministers of Israel) and Leonid Hurwicz (mathematician who won the Nobel prize on Economics in 2007) studied there.
The university is proud to maintain its traditions. Since its foundation, the admission process remains the same. The university has M courses in all fields of knowledge, each of them offer a number of openings, and N candidates who must decide how many courses are of their interest. Furthermore, each candidate must rank the courses he wants, from the ones he wants the most and to the ones he desires the least. The courses that are not ranked by a candidate are not considered when assigning a course to this candidate, even if there are openings remaining.
A series of tests are given to each candidate (the same for everybody), and each one gets a score. This score will be used to decide which course a candidate goes to. The candidates are considered in decreasing order of their score and will be assigned the first course (using their preferences) that has spots left. Ties are broken using the preferences. If two candidates are tied, and both want the same course, but this course is in 3rd place in one list and in 10th place in the other list, the position is given to the one that wants it the most. In case the tie remains, the opening is given to the candidate that signed up first.
Your task is to write a program that makes the selection of the candidates to the Warsaw university.
The first line contains two integers N and M, the number of candidates and the number of courses, respectively. The courses are identified by the integers from 1 to M. The second line contains integers V1, V2, ..., VM where Vi represents the number of openings in course i.
In the following N lines is given the information of the N candidates in the order they signed up. The ith line contains, in this order, an integer Pi indicating the score of candidate i and and integer Qi indicating the number of courses he is interested in, followed by a list of Qi space separated distinct integers, the list of courses given in the order of his preference (starting with the most wanted).
Limits
- 1 ≤ N, M ≤ 103
- 1 ≤ Vi ≤ 103
- 0 ≤ Pi ≤ 100
- 0 ≤ Qi ≤ 103
- Each number in the list is between 1 and M
Print N integers, the ith one is the course chosen for candidate i. If a candidate could not get a spot in any of the course he was interested, print - 1.
4 2
5 2
87 1 2
89 2 2 1
88 2 2 1
40 2 1 2
-1
2
2
1
3 2
1 1
99 2 1 2
100 1 1
99 2 2 1
-1
1
2
4 3
1 2 1
76 3 1 2 3
76 3 1 2 3
76 3 1 2 3
76 3 1 2 3
1
2
2
3
Gdanks city became known worldwide in the early 80's by the work of the Solidarność (Solidarity) syndicate, led by Lech Wałȩsa,, who became president of Poland years later. At that time, Walesa dealt with the communism regime. He started a process that helped to finish the communism in Eastern Europe at the late 80's.
Wałȩsa was a leader that never got late. He was known for attending several syndicate's meetings and never leaving during a meeting. However, he demanded the starting and finishing times of each meeting, in order to prepare his agenda. Each committee published the stating and finishing time of its meeting. Walesa chose the meetings that he was going to attend each day in such a way that he would attend as many meetings as possible.
Your task is to make a program that receives a list of meetings and chooses a subset of meetings that doesn't overlap and with maximum size, following Wałȩsa's preferences.
The first line contains a number N of syndicate's meetings. The meetings are identified by integers from 1 to N in the order they are given in the input. The following N lines contain the starting and finishing times (in this order) of a meeting in the format HH : MM (exactly two digits for each). You can start a meeting the same minute you end another meeting. All the meetings start and finish in the same day. It is guaranteed the end time is after the start time.
Limits
- 1 ≤ N ≤ 105
- 0 ≤ HH ≤ 23
- 0 ≤ MM ≤ 59
For each instance print the list of meetings chose by Wałȩsa. The meetings must be printed in the order of its starting time. If there are multiple possible answers, print any of them.
3
08:15 08:45
08:00 08:30
08:30 09:00
2 3
5
11:00 12:00
12:20 13:15
10:10 12:15
12:30 13:00
10:30 12:16
1 4
3
15:23 16:02
15:00 16:02
15:27 16:02
2
Every weekend, Pedro and his friends reunite to play a RPG (Role Playing Game). In a RPG one of the friends, called gamemaster, tell a story in which the other players interact according to some predefined rules and using the results from rolling dice. Pedro, being the most experienced in this game, is always the gamemaster. He always design the games beforehand in order to entertain his friends the most.
The next weekend, Pedro is going to host the continuation of last's weekend game. This time N monsters numbered from 1 to N are going to appear, one after another. The difficulty of a monster is determined by M attributes (strength, speed, intelligence, etc). Now, Pedro must decide against which of these monsters his friends will fight. A sequence of monsters is valid if its indices are in increasing order. Pedro's friends are really intelligent and will be disappointed if they fight against a monster that is not harder than all the monsters that they have already fought. A monster is harder than another monster if it has a higher value in each attribute than the other monster.
Pedro would like the game to last as long as possible. He knows you compete in programming contests, so he asked for your help. You have to choose a subset, with the biggest number of monsters possible, to battle against your friends (obeying the restrictions given before).
The first line has two integers M and N, the number of attributes and monsters, respectively. The following M lines will contain N integers each. The jth integers in the ith line represents the value of the jth attribute of the ith monster.
Limits
- 1 ≤ M ≤ 10
- 1 ≤ N ≤ 105
- If M > 2 then N ≤ 103
- The value of an attribute of a monster is between 0 and 109
Print a line containing the indices of the monsters, in order of difficulty. If there are multiple answers, any one will be accepted.
3 4
1 2 9 7
1 3 4 9
1 9 5 6
1 2
4 4
0 3 3 4
0 1 2 4
0 2 1 4
0 3 3 4
1 3 4
Karol Wojtyla was born in Wadowice in 1920. He was elected as pope John Paul II in 1978 and died in April 2th in 2005, after completing 26 years of papacy. He is one of the most important polish men in history.
Before devoting his life to religion, during the World War II, he worked in a factory of chemical products. One of his duties was to arrange boxes containing chemical products in stacks. The problem was that some of these boxes were really heavy, and others could not afford much weight over them. The managers of the factory wanted big stacks, with the highest number of boxes possible. Every box had associated two attributes: its weight (in kilograms) and the weight that it is able to afford in kilograms (including the weight of the box). For example, a box of 25 kg. and 60 kg. of resistance is able to hold at most 35 kg. on top of it.
Your task is, given a list of boxes, along with their weight and resistance, determine the maximum number of boxes that can be arranged into a stack without exceeding the resistance of any of them.
The first line contains an integer T, the number of test cases.
The first line of each test case contains an integer N, the number of boxes. Each of the next N lines contains two integers, the ith has Wi and Ri, the weight and the resistance of box i, respectively.
Limits
- 1 ≤ T ≤ 25
- 1 ≤ N ≤ 103
- The sum of N over all test cases will not exceed 3·103
- 1 ≤ Wi ≤ 103
- Wi ≤ Ri ≤ 106
For each test case, print the maximum number of boxes that can be arrange into a stack.
2
4
13 30
11 15
7 28
6 6
3
43 60
47 100
430 450
3
2