All provident tourists know about low-cost airlines. Those who used them at least once also know that their airfare usually includes neither lunch nor luggage.
Naturally, tourists don't want to overpay luggage fee, therefore they distribute their luggage so that it satisfies all airline requirements.
A certain tourist prepaid three luggage slots. Then he calculated the number of different ways K to distribute weight N among these three slots so that all luggage is packed, none of the slots are empty and all weights are integers. The order of the slots does not matter, so, for example, two distributions 2, 2, 1 and 2, 1, 2 are considered the same.
After landing, the tourist realised that the airline lost all his luggage! And while filling in a lost and found application, he found out that he does not remember the weight of each slot. He remembered only the fact that the number of ways K to pack the luggage was at least L and did not exceed R.
You need to calculate number of possible integer total weights N that could have been in the tourist's luggage.
The single line of input holds two integer numbers L and R (1 ≤ L ≤ R ≤ 1017): the minimum and maximum number of ways to distribule the luggage in three slots.
Output a single integer: the number of possible total weigths N that could have been carried by the tourist.
2 4
3
In the example, the tourist could have carried the total weight of 5, 6 or 7.
No one is safe from losing his passport. But even if the passport is lost, it is still not the end of the world. To replace it, you just need to present another picture ID and wait for a few weeks. But what should one do if the passport is suddenly lost during a vacation in an exotic country?
The migration service of a certain insular country keeps track of every single tourist entering the country. Each tourist is assigned a sequence of K fields which all together create a tourist ID. When a tourist crosses the border, the fields are filled according to the data in the passport. The tourist ID is a complex concept to handle for migration officers, so one can not be sure which fields will contain one's name or surname, or whether they will be present in it at all. It may even happen that migration officers fill some fields with arbitrary strings by mistake. The only thing known for sure is that none of the fields are empty and all fields contain only lowercase English letters.
A certain tourist tries to find his tourist ID by issuing queries to the migration service database using a query form. Each query consists of K strings. The answer for the query is the list of all tourist IDs in the database for which each of the K strings is a prefix of the corresponding field of that tourist ID.
Initially, all K strings of the query form are empty. To make the next query, the tourist modifies the previous one in one of the two following ways:
- <i> + <c>: add character <c> to the end of string number <i>,
- <i> -: remove the last character of string number <i>.
For each of the Q queries, you need to calculate how many tourist IDs match this query.
The first line of the input holds an integer number N (1 ≤ N ≤ 100 000) which is the number of tourist IDs in the database and an integer number K (1 ≤ K ≤ 3) which is the number of fields in each tourist ID.
Then follow N tourist IDs. Each tourist ID is given on K consecutive lines, each of which contains the respective field of the tourist ID. It is guaranteed that the lines are non-empty and contain only lowercase English letters. The total length of all given strings does not exceed 100 000.
The next line holds a single integer Q (1 ≤ Q ≤ 100 000) which is the number of queries. Each of the next Q lines describes a modification to the query form. Each modification has one of the two possible forms: either "<i> + <c>" or "<i> -". It is guaranteed that before each modification of the second type, the respective field is not empty.
For each query, print the number of matching tourist IDs in the database on a separate line.
5 2
abacaba
ccad
abadaba
cbad
abbbaaa
cbab
bbbba
ccc
abacabs
fuuuu
15
1 + a
2 + c
2 + c
1 + b
2 -
2 + b
1 + a
2 -
2 -
1 -
1 -
1 -
1 + c
1 -
1 + b
4
3
1
1
3
2
1
2
3
4
4
5
0
5
1
One of the oldest existing buildings on Earth is the English Stonehenge. Nobody knows its purpose: some say it was an ancient sanctuary, other say a huge observatory. But recently, archeologists found another piece of the puzzle: an ancient tropical stonehenge.
The tropical stonegenge, unfortunately, was severely damaged by lianas. Fortunately, scientists managed to identify places of all stones of the building except one. The only thing that can help to find the position of the last stone is an ancient manuscript found nearby.
The manuscript tells the following.
- Tropical slonehenge is a convex polygon with N vertices with an ancient stone in each vertex.
- No three vertexes lie on the same straight line.
- All vertices have integer coordinates, the coordinates do not exceed 106.
- The area of the polygon is equal to S.
Knowing the coordinates of N - 1 stones and the total area S, find the coordinates of the last stone.
The first line of input holds an integer number N (4 ≤ N ≤ 105) and the area of the polygon S. The area is a real number given with exactly one decimal digit (1 ≤ S ≤ 4 × 1012). The next N - 1 lines hold coordinates of the known stones in the form X Y (|X|, |Y| ≤ 106). The stones are listed in counterclockwise order of polygon traversal, excluding the missing one.
Output the coordinates of the missing stone in the form X Y. It is required that the coordinates are integers and |X|, |Y| ≤ 106. In case of multiple solutions, output any one of them. It is guaranteed that the judges' inputs are constructed in such a way that there is at least one possible solution satisfying the constraints above.
4 4.0
0 0
2 0
0 2
1 -2
5 10.0
5 3
1 3
2 1
4 1
1 5
Exactly N years ago, a new highway between two major cities was built. The highway runs from west to east. It was planned as one big segment of a toll road. However, new highway was not popular: drivers still used free roads.
After analyzing the situation, the administration decided to perform a marketing trick to increase the popularity of the new highway.
The highway was divided into segments. Initially, there was only one segment. Every odd year, each of the existing segments was divided into two new segments with lengths divided as X: Y. This means that the length of the western segment relates to the length of the eastern segment as X relates to Y. Every even year, each of the existing segments was also divided into two new segments, but this time, the ratio was Y: X. After each division, the first of the two resulting segments was declared a free road and the second one a toll road. Each year, the segments are numbered from 1 from west to east. For simplicity, X and Y are positive integers which sum up to exactly 100.
As a result, the administration was able to significantly increase the income: the drivers started to drive on free segments and did not dare to turn away at the sight of the next toll segment. But after N years, the plan of the highway became so complex that it is now hard to calculate the exact lengths of the segments.
Knowing the total length of the highway P, one can calculate the length Lk of the segment with number k using the formula
You need to answer to the queries containing numbers Ki of segments. To answer each query, you must print the values of Aki and Bki for the corresponding segment.
The first line of the input contains three integers: the number of years N (1 ≤ N ≤ 1018) that have elapsed since the highway was built, followed by the percentages X and Y (1 ≤ X, Y ≤ 99, X + Y = 100) used each year to divide the segments.
The second line contains one integer: the number of queries Q (1 ≤ Q ≤ 104).
The following Q lines contain queries. Each query is an integer Ki (1 ≤ Ki ≤ 1018), the number of some segment. It is guaranteed that the segment with such number exists.
For each query, print two integers Aki and Bki on a separate line.
3 25 75 4
1
3
5
8
2 1
3 0
1 2
1 2
The longest escalator in the world is located in Hong Kong. Unlike conventional escalators in the subway, this escalator goes right down the street and was built in order to reduce the number of traffic jams in the city. Now it carries tens of thousands of people every day.
Travelling in Hong Kong, a certain tourist decided to use the escalator to go down. He was surprised when it turned out that the escalator is going only up. The escalator was empty, so the tourist decided to try to walk down to the bottom. But as soon as the tourist began his movement, the passengers began to enter the escalator from the bottom...
The escalator runs upwards at a constant speed; the tourist moves downwards with constant speed which exceeds the escalator's speed by absolute value. At any given time, each person (our tourist or some other passenger) is either on the left side of the escalator or on the right side.
For each passenger who will meet the tourist before the end, we know the side initially selected by him and the probability that he changes the side: each second, the passenger changes the side he is currently standing at to the opposite one with that probability. Moreover, for each passenger, we know the time interval Ti in seconds between entering an escalator and meeting with the tourist. Thus, during the time interval of Ti seconds, the passenger will make a decision whether to change the side exactly Ti times.
The tourist starts moving on the left side and will change the side only if otherwise he will run into a passenger.
You need to find the expected number of times that the tourist will change the side before he will finish his journey at the bottom.
Tourist can be considered thin enough so that he can pass between passengers who stand on adjacent stairs at different sides. The time used by the tourist to change the side is negligible.
The first line of the input contains the integer N (1 ≤ N ≤ 105) which is the number of passengers coming to the bottom of the escalator.
Each of the following N lines contains a description of the passenger which consists of the following three pieces. First comes the time interval Ti in seconds (1 ≤ Ti ≤ 106) between the moment when the passenger entered the escalator and the moment he meets the tourist. Then goes a character Ci which is either "L" if the passenger starts at the left side or "R" if he starts at the right side (sides are given relative to the tourist). It is followed by the probability of side change Pi (0 ≤ Pi ≤ 1) given with no more than three digits after the decimal point. All values of Ti in the input are pairwise different.
Passengers in the input data are listed in the order in which they enter the escalator, that is, in decreasing order of Ti.
Print the expected number of side changes made by tourist with absolute or relative error no more than 10 - 6.
2
5 L 0.5
1 R 0.4
1.000000000000
Mexico is one of the most interesting countries for tourists. Endless sandy beaches, unique culture, ancient Indian temples... Beautiful nature: tropical forests, mountains, deserts... And, of course, cacti!
A certain tourist arrived in Mexico and decided to explore the country. For this, he rented a car and made a plan for visiting the cities of the country on K days ahead.
We know that in Mexico, there are N towns connected by M roads. Each road connects two different cities, and no two roads connect the same pair of cities. All roads have the same length and are bidirectional, and it is possible to travel by road network from each city to any other.
In addition, if you look at a road network of Mexico as a graph where vertices are cities and roads are edges, this graph will be a vertex cactus: a connected undirected graph in which each vertex belongs to at most one simple cycle.
The tourist begins his journey through the cities of Mexico in city 0. Following the plan, on each day, he chooses a city for the excursion and drives to it from the city in which he was the previous day by the shortest route. If the city does not change, the tourist continues the excursion in the current city.
Each time when the tourist is driving somewhere, he should refuel the car in the city that is closest to the middle of his path. If there are several such cities, any of them can be selected.
Given the road map of Mexico and the numbers of cities that tourist plans to explore, determine the cities, in which he will refuel his car.
The first line of the input contains two integers: the number of cities N (1 ≤ N ≤ 105) and the number of roads M.
Each of the next M lines describes one road and contains two integers Ui and Vi (0 ≤ Ui, Vi ≤ N - 1) which are the cities connected by i-th road.
The next line contains an integer K (1 ≤ K ≤ 105) which is the number of cities which the tourist plans to visit.
The next line contains K integers: the numbers of these cities in the order in which he plans to visit them.
Print K integers: the numbers of cities in which the tourist will refuel his car, listed in the order of refueling events. In case there are several solutions, print any of them.
6 6
0 1
0 2
2 3
3 4
2 4
4 5
5
5 1 3 3 4
4 2 0 3 4
The National Library of France is one of the largest libraries in the world. But not only collections of rare books attracts tourists there. Many of them visit the library just to use the free Wi-Fi...
The library building can be represented as a rectangular field consisting of N × M cells. Each cell can be one of three types:
- an obstacle denoted by "#",
- a corridor denoted by ".",
- a room denoted by a digit from 1 to 5 depending on the room type (the numbers may be repeated).
Visitors can pass between any two cells that share a side, but can not pass into any cell with an obstacle.
Wi-Fi coverage in the library is quite weak, so in the rooms and corridors, there are some visitors with gadgets that are walking around the library looking for a place with good signal strength.
A certain tourist came to the library with his friends to use the free internet, and after a long search, he found a place with good signal strength. Due to poor knowledge of French language, the tourist had troubles to identify this location. Nevertheless, he decided to tell his friends about this place and went out in search of them. To remember his path, he decided to record how many cells and in what direction he passed. Also, he decided to record a sequence A of room types he visited, but this part was not treated very carefully, so he may miss the numbers of some visited rooms.
While the tourist was trying to find his friends, he was forced to leave the building because it was late and the library has closed.
The next day, the tourist went to the library again. Given the map of the library, he decided to find the same place again.
The room must satisfy the following criteria:
- If the tourist starts the movement from this room and strictly follows his records, he will never walk out of the library or go try to move into an obstacle.
- If the tourist will record the sequence B of visited room types during his way, A must be a subsequence of B.
You need to determine how many rooms in the library will satisfy the criteria above.
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 1000) which are the horizontal and vertical dimensions of the library's map.
Then map itself follows: each of next N lines contains exactly M characters. Valid characters are "#", ".", "1", "2", "3", "4" and "5". The lines are ordered from top to bottom, the characters in each line are ordered from left to right.
Then follows a line containing the number of tourist's movements K (1 ≤ K ≤ 100).
The following K lines specify the tourist's movements. Each movement is described by a pair of integers Ci and Pi where Ci is a character indicating the direction of travel ("L" for moving to the left, "R" to the right, "U" up and "D" down), and Pi (1 ≤ Pi ≤ 999) is the number of cells travelled in the given direction.
The last line contains a sequence A of digits: the types of rooms listed by tourist on the first day (1 ≤ |A| ≤ 100, 1 ≤ Ai ≤ 5).
Print one integer: the number of rooms, which satisfy all requirements from the problem statement. Note that it may happen that the tourist made an error recording the sequence A. In that case, the number of rooms satisfying the requirements may be zero.
4 5
22.#.
1211#
..#.1
.#122
2
L 2
U 1
121
1
4 5
..3#.
213.#
.#33#
1214.
3
L 1
R 2
U 1
1213
3
In the first example, only the room (2, 3) in row 2 and column 3 fits.
In the second example, three rooms fit: (2, 2), (4, 2) and (4, 3).
While traveling to England, it is impossible not to catch the English passion for football. Almost everyone here is involved in football life: some play, others are watching, and the most risky ones bet on the results.
Before the start of the next season of English Premier League, a certain bookmaker office has launched a new option. In order to participate, players must bet a fixed (same for all) amount of money on one of the N teams participating in the championship. All players who guessed a team that will be the champion get back their owh bets. Additionally, they share equally one half of all bets made on the other teams.
During this event, at least one player made a bet, each player made exactly one bet on some of the teams, no teams received more than K bets, and at the end of the tournament, the bookmaker's office reported a profit of exactly P percent of the total amount of bets.
Find any distribution of bets between teams which satisfies the above requirements, or determine that no such distribution exists.
The input contains one line with three integers N, K and P: the number of teams in the football tournament, the maximum possible number of bets on the one team and the profit reported by the bookmaker's office (2 ≤ N ≤ 100, 1 ≤ K ≤ 100, 0 ≤ P ≤ 100).
If no distribution satisfying the requirements exists, print 0 on a separate line.
Otherwise, on the first line, print one integer W: the number of the winning team (1 ≤ W ≤ N). The second line must contain N integers A1, A2, ..., AN where Ai is the number of bets on i-th team (0 ≤ Ai ≤ K). Note that the team order is arbitrary, but the number of winning team must fit this order. If there are several solutions, print any one of them.
4 100 10
2
10 80 5 5
2 4 40
1
1 4
5 10 23
0
Dragobat is the highest and the most elite ski-park of Ukraine. Apart from beautiful pine forest and breathtaking view, it is famous for its lacet roads.
The main road starts in the Yasinya-village (A) and ends in Dragobat (B). At the zero moment, two cars start to move from point A to point B and from point B to point A respectively. As soon as a car reaches its destination, it disappears from the road, and another car starts moving from the starting point. There are no other cars on the road. As a result, there are at most two cars on the track at any given moment of time.
The total length of the road is L. The road is split into one-lane and two-lane segments of given lengths Hi such that 
. The first and K-th segments are two-lane, and each pair of adjacent segments has a different number of lanes. Points A and B are located outside the road. Both one-lane and two-lane segments of the road are adjusted by the center of the road (see the image below).
A car is a square 1 × 1 which moves by the following rules:
- sides of the car are always parallel to the axes;
- the car which started from point A is always moving by the lower side of the road;
- the car which started from point B is always moving by the upper side of the road;
- the absolute value of X-speed of each car is equal to 0 or 1 at any given moment of time, the speed changes momentarily;
- you can ignore the time spent by cars to move among the Y axis (while changing from one-lane to two-lane and backwards).
If two car-squares intersect (have positive area of their intercestion), an accident is registered.
On the picture above, case 1 won't lead to an accident.
In case 2, an accident can happen if the upper car will start to move on to the one-lane part of the road before the lower car will pass the upper car.
In case 3, an accident will happen if none of the cars change their direction to the opposite.
Because of heavy snowfalls, cars can only see each other if the distance by the X-axis doesn't exceed R. A car can not be seen if it is still in point A or B.
When two drivers can see each other, they try to avoid any possible accident using the following rules:
- Go on moving with initial speed if it won't lead to an accident.
- If the current speeds of the cars will lead to an accident, then one of the cars should change its speed, while the second one should keep the initial speed. The driver which adjusts the speed is determined in such a way that the time of passage is minimal possible. If the time of passage is equal, the driver which started at point B changes its speed.
The time of passage is an interval of time between the moment when drivers first see each other and the moment when the car started in A will be to the right of the car started in B.
Calculate the number of cars which have successfully moved from A to B and from B to A at the moment T. A car arrives to the village only after it completely leaves the road.
The first line of input holds the time T (1 ≤ T ≤ 109) and the visibility radius R (1 ≤ R ≤ 106). The second line holds an odd number K (1 ≤ K ≤ 1000) which is the number of segments of the road. The third line holds K numbers Hi (2 ≤ Hi ≤ 1000) which are the lengths of the road segments. All numbers in the input are integers.
Output two integers: the number of cars which have successfully moved from A to B and the number of cars which have successfully moved from B to A at the moment T.
40 2
5
2 2 2 4 2
2 3
30 7
3
2 2 2
3 3
In the first example, cars will arrive at village B at moments 15 and 28, and at village A at moments 13, 26 and 39.
In the second example, cars will arrive at village B at moments 7, 15 and 23, and at village A at moments 11, 19 and 27.