There are three identical servers and n requests to process. The time to process each request is known: it takes ti seconds to process the i-th request on any server.
You want to assign requests to servers in the most fair way. For each server, find its load: the total time required to process all requests assigned to this server. The assignment is the most fair if the difference between maximum and minimum load of the three servers is as small as possible.
The first line contains an integer n (1 ≤ n ≤ 400), the number of requests. The second line contains the sequence of integer numbers t1, t2, ..., tn (1 ≤ ti ≤ 30) where ti is the time to process the i-th request.
Print four lines. The first line must contain the smallest possible difference between the maximum and minimum load of servers. Each of the following three lines must contain the description of requests assigned to a server. A description must start with the number of assigned requests, followed by the indices of these requests in any order.
If there are several possible answers, print any one of them.
6
7 3 20 1 5 7
9
1 3
3 2 4 1
2 5 6
3
7 7 7
0
1 3
1 2
1 1
This is an interactive problem.
You are given a bipartite graph with n vertices in the first part and m vertices in the second part. There are zero or more edges in the graph as well. Multiple edges are allowed. There is also a peg which is initially placed in one of the vertices of the first part. Two players are playing a game on this graph: on each turn, they move the peg along a graph edge. After the peg is moved along an edge, this edge disappears. The player who cannot make a move loses the game. The first player starts the game.
You are given the graph and the initial position of the peg. Your task is to write a program which will play this game as the first player. The jury's program will play as the second player, and it will win the game whenever it is possible. Your program should also win the game whenever it is possible. If it is impossible to win, your program should play until the game ends.
Your opponent's moves will be provided in interactive mode: after each of your moves, you will be given your opponent's next move. Please be sure to use the stream flushing operation after each of your moves to prevent output buffering. For example, you can use "fflush(stdout)" in C or C++, "System.out.flush()" in Java and "flush(output)" in Pascal.
The first line contains four integers n, m, e and v (1 ≤ n, m ≤ 50, 0 ≤ e ≤ 2500, 1 ≤ v ≤ n): the number of vertices in the first part of the graph, the number of vertices in the second part, the number of edges and 1-based number of vertex in the first part where the peg is placed initially.
Next e lines describe edges. Each of these lines contains two numbers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) separated by a single space, denoting an edge between vertex x of the first part of the graph and vertex y of the second part.
After that, you will be given the opponent's moves. Each move is a 1-based integer vi (1 ≤ vi ≤ n), the number of the vertex in the first part of the graph where your opponent moved the peg.
If you cannot make the next move, just print the phrase "Player 2 wins" on a separate line and terminate your solution gracefully. If a move is possible, print a line with a single integer: the number of vertex in the second part of the graph where you move the peg. If after your move, the opponent cannot make a move, additionally print the phrase "Player 1 wins" on a new line and terminate your solution gracefully. Do not forget to flush the output buffer after each of your moves.
Each time there are several possible moves, you can pick any one of them, provided that you still win in the end if you initially could.
3 2 5 3
1 1
1 2
2 1
2 2
3 2
1
2
2
1
2
Player 1 wins
2 2 3 1
1 1
1 2
2 2
1
Player 1 wins
2 2 6 1
2 2
2 2
1 1
1 2
2 1
2 2
2
1
1
2
Player 2 wins
You are given a chessboard of size n × m. The cells are painted black and white such that the cell (1, 1) is white, and any two adjacent cells have different color. Some cells of the chessboard are banned.
Your task is to find a connected figure on the chessboard which does not contain banned cells and contains exactly w white cells and b black cells. Two cells are adjacent if they share a side.
The first line contains three integers n, m and k (1 ≤ n, m ≤ 10, 0 ≤ k ≤ n·m): the number of rows of the chessboard, the number of columns of the chessboard and the number of banned cells.
The following k lines contain the coordinates of banned cells. Each of these lines contains a pair of integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m): the coordinates of a banned cell. All banned cells are distinct.
The last line contains two integers w and b (0 ≤ w, b ≤ n·m, w + b > 0).
If it is impossible to find a connected figure without banned cells with w white cells and b black cells, print a single line containing ":-(" without quotes.
Otherwise, print n lines containing m characters each which describe the figure. The lines must consist of characters "O", "X" and ".":
3 4 2
2 2
2 3
3 3
....
X..O
OXOX
8 10 1
1 5
19 9
..........
..X...XOX.
..O...O...
..XO.OXO..
..O.O.O.O.
.OXOXOXOXO
..O.O.O.O.
..........
Everyone has seen something like this a lot of times:
Suppose that you have several rods connected by their ends in a line in a certain order. The connections are non-stretchable and flexible, that is, each two successive rods can join at any angle. The rods are very thin, so they can be treated as line segments. The mass is uniformly distributed along each segment. Moreover, all the segments have the same density, so their masses are proportional to their lengths.
The first line contains two integers n and L (3 ≤ n ≤ 10, 200 ≤ L ≤ 299). The second line contains n integers l1, l2, ..., ln (100 ≤ li ≤ 199), the lengths of the segments from left to right. It is not allowed to change the order of the segments.
Output n - 1 lines. Each line must contain two real numbers, presenting x and y-coordinates of the points of the polyline from left to right. Do not output the first and the last points (0, 0) and (L, 0).
Please print the numbers with at least three digits after the decimal point.
3 200
100 100 100
50.0000000000 86.6025403784
150.0000000000 86.6025403784
3 241
128 105 108
76.2967704600 102.7754971643
180.4447346423 89.4262815813
The main office of the Berland Bruteforce Corporation consists of n rooms, connected by n - 1 passages. There is exactly one way to travel between any pair of rooms using these passages (seeing this phrase, one who is familiar with the graph theory immediately recognizes an undirected tree). Let's assume that the rooms are numbered with consecutive integers from 1 to n. There are ei employees working at room i. For each passage, its length (in meters) is known.
The recent earthquakes have convinced the board of BBC to create an evacuation plan for the employees. In a plan, there should be a single evacuation point, which may be located either at some room or at any place in a passage. In the latter case, a new room is created. This new room divides the passage of length L into two passages of lengths L1 and L2 (L1 + L2 = L).
Once the evacuation point is set, the evacuation happens as follows. At the time 0 (the beginning of evacuation), all employees simultaneously try to start moving towards the evacuation point. It takes exactly s seconds for a person to walk 1 meter. Passages have limited capacity c, which is the same for all passages: at most c persons can enter the passage at a time step. Let us clarify this a bit. Consider some passage. It is clear that people will move through it only in one of the two possible directions. At time 0, at most c persons can enter the passage. Then, nobody can enter the passage until time 1, when again at most c persons can enter the passage, an so on. There is no limit on the number of persons that can be in a room or in a passage at the same moment of time.
The BBC board is interested in such a plan that minimizes the time of the evacuation: the time when every person reaches the evacuation point. Help them to create it.
The first line contains three integers n, c and s (1 ≤ n ≤ 105, 1 ≤ c ≤ 104, 1 ≤ s ≤ 100): the number of rooms, the capacity of each passage and the time needed to walk 1 meter. The second line contains n integers e1, e2, ..., en (1 ≤ ei ≤ 106). Each of the next n - 1 lines contains three integers u, v and d (1 ≤ u, v ≤ n, 1 ≤ d ≤ 104), meaning that there is a passage of length d meters between rooms u and v.
Print the optimal location of the evacuation point. If you are going to place the point in an existing room, print its number. Otherwise, print three numbers u, v and x, meaning that the evacuation point must be placed in the passage connecting rooms u and v at the distance of x meters from u. The number x must belong to the interval (0, l) where l is the length of the passage between u and v.
Your answer will be considered correct if the evacuation time in your plan has an absolute or relative error of at most 10 - 9 from an optimal one.
2 2 1
5 5
1 2 3
1 2 1.500000000000
2 2 1
5 10
1 2 3
1 2 2.500000000000
3 2 10
8 6 8
1 2 10
2 3 10
2
4 3 1
3 8 4 7
1 2 2
2 3 1
2 4 5
2 4 1.500000000000
Let's go through the evacuation in the fourth sample step-by-step.
Evacuation finishes in 5.5 seconds.
There are n empty vessels on a river bank. The i-th vessel can contain at most ai liters of water. Almighty Ivan needs to fill some vessel with exactly A liters of water and take it home. To do so, he can perform the following operations:
Now Almighty Ivan needs your help. You should provide him with the list of operations which leads to the situation when one of the vessels contains exactly A liters of water. If there is no way to do so, print - 1.
Please note that you don't have to minimize the number of operations in this list, but the number of operations should not exceed 106.
The first line contains integers n and A (1 ≤ n ≤ 10, 1 ≤ A ≤ 5) — the number of vessels and the required number of liters. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2·104) where ai is the volume of the i-th vessel.
If the answer doesn't exist, print - 1.
Otherwise, on the first line, print one integer m: the number of operations in the list. Then print m lines: the descriptions of the operations.
The description of each operation must start by an integer specifying its type (1, 2 or 3 as they are listed in the statement). For the first and second type, it must be followed by one integer number k (1 ≤ k ≤ n) which is the index of the vessel taking part in this operation. For the third type, it must be followed by two integer numbers i and j (1 ≤ i, j ≤ n, i ≠ j) which mean that Ivan should pour water from the i-th vessel to the j-th one until one of them is full or empty.
Please check the samples for better understanding.
2 1
5 2
4
1 1
3 1 2
2 2
3 1 2
4 3
1 2 1 1
-1
Find the number from the range [a, b] which has the maximum product of the digits.
The first line contains two positive integers a and b (1 ≤ a ≤ b ≤ 1018): the left and the right ends of the range.
Print the number with the maximum product of the digits from the range [a, b]. If there are several possible answers, print any one of them.
1 10
9
51 62
59
The Biathlon 2.0 World Championship is held in Petrozavodsk in 2016.
Biathlon 2.0 has different rules than the classic one. The racing track consists of n segments. The i-th segment consists of ai kilometers to travel and bi targets to hit. To pass a segment, an athlete must travel all ai kilometers and hit all bi targets. Athletes pass segments in the order from 1 to n. Each athlete must carry a rifle with him. It is allowed to change rifles between segments.
The national team of Berland has m different rifle types at its disposal. Each rifle type is described by two numbers: ci and di, where ci is the number of seconds needed to travel one kilometer with a rifle of this type and di is the number of seconds needed to hit one target with a rifle of this type. The team has an unlimited supply of rifles of any type.
Your task is to ensure Berland victory and find a rifle for each track segment to minimize the number of seconds needed to pass the segment.
The first line contains one integer n (1 ≤ n ≤ 5·105), the number of segments in the track. Each of the next n lines contains two integers ai and bi (0 ≤ ai, bi ≤ 109, ai + bi > 0), the number of kilometers and targets on the i-th track segment.
The next line contains one integer m (1 ≤ m ≤ 5·105), the number of rifle types used by the national team of Berland.
The next m lines contain two integers ci and di (1 ≤ ci, di ≤ 109), the number of seconds needed to travel one kilometer with the i-th rifle type and the number of seconds needed to hit one target with the i-th rifle type.
Print n space-separated integers. The i-th integer must be the number of seconds needed to pass the i-th segment if an optimal rifle is used.
3
1 4
4 1
3 3
3
1 3
3 1
2 2
7 7 12
1
1000000000 1000000000
1
1000000000 1000000000
2000000000000000000
Professor Tupids has found a mysterious manuscript during his recent archaeological expedition.
The manuscript, in fact, looks like a series of symbols with meaning yet to be discovered. In order to simplify studying of the manuscript, professor Tupids created an alphabet of all symbols occurred (let's denote their number as c) and replaced each symbol with its position in the alphabet (positions are numbered from one). So, the manuscript became represented as a list of n integers from the segment [1;c].
Professor's intuition told him that the key to understanding the manuscript is to find some regularities in locations of the symbols. So he wrote down a huge table with n rows and c columns, where cell at i-th row and j-th column contained the position of the next occurrence of symbol number j after the position i (the cell was left empty if there were no appropriate occurrences).
But then a disaster happened: a fire in the laboratory completely destroyed the manuscript! Fortunately, the table built by professor was salvaged, though it was damaged to some extent. Not only some of the cells were lost in the fire, but, thanks to the careless assistants, cells in each of the rows were reordered arbitrarily!
Professor Tupids doesn't want to lose face in the scientific community, so he asks you to help him with restoring the original manuscript, given the remaining information from the table. As there may be infinitely many different solutions (even the size c of the alphabet was lost!), professor wants you to restore the lexicographically smallest solution. It is not guaranteed that the solution exists, though, as the table could have been completely spoiled by the assistants.
The first line contains a single integer n (1 ≤ n ≤ 3·105), the length of the original manuscript. After that, n lines follow, the i-th of which contains an integer ci (0 ≤ ci ≤ n - i) followed by ci distinct integers from the segment [i + 1;n]: the contents of the survived non-empty cells of the i-th row of the table in arbitrary order.
It is guaranteed that the sum of all ci (1 ≤ i ≤ n) does not exceed 3·105.
If the solution exists, print a single line with n positive integers: the representation of the lexicographically smallest manuscript. Otherwise, print "No solution" (without quotes).
4
3 2 3 4
2 4 3
1 4
0
1 1 2 3
5
1 2
1 4
1 4
1 5
0
1 1 1 2 1
Valera has only one electrical socket in his flat. He also has m devices which require electricity to work. He's got n plug multipliers to plug the devices, the i-th plug multiplier has ai sockets.
A device or plug multiplier is supplied with electricity if it is either plugged into the electrical socket, or if it is plugged into some plug multiplier which is supplied with electricity.
For each device j, Valera knows the safety value bj which is the maximum number of plug multipliers on the path between the device and the electrical socket in his flat. For example, if bj = 0, the device should be directly plugged into the socket in his flat.
What is the maximum number of devices Valera could supply with electricity simultaneously? Note that all devices and plug multipliers take one socket to plug, and that he can use each socket to plug either one device or one plug multiplier.
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105), the number of plug multipliers and the number of devices correspondingly.
The second line contains n space-separated integers a1, a2, ..., an (2 ≤ ai ≤ 2·105). Here, the number ai stands for the number of sockets on the i-th plug multiplier.
The third line contains m space-separated integers b1, b2, ..., bm (0 ≤ bj ≤ 2·105). Here, the number bj stands for the safety value of the j-th device.
Print a single integer: the maximum number of devices that could be supplied with electricity simultaneously.
3 5
3 2 2
1 2 2 1 1
4
3 3
2 2 2
1 2 2
3
There are n cities in the country of Flatland, n - 1 bidirectional roads connect some pairs of Flatland's cities. It is possible to get from any city to any other city of the country using roads. In this problem we will refer to the smallest set of roads needed to travel from a to b as a simple path.
The government of Flatland has recently introduced payment tolls on all roads. Using one road connecting two cities costs one ruble. That means that every time when you travel from one city to another one, you have to pay as many rubles as the number of roads you pass during your journey.
Many people got upset because of this decision, especially people who travel long distances. Political opponents of the current government claim that the maximal cost of a simple path in Flatland is very high, namely 
rubles. The government has decided to support people and calm down the opposition. They want to reduce the maximal cost of a simple path in the country as much as possible. In other words, they want the number reported by the opposition to be the lowest possible. The government will allow to remove tolls from at most k roads in order to achieve that. If there are multiple ways to do that, they want to minimize the number of roads that will become free.
Like any other government, Flatland's one is quite inflexible. They additionally require that it should be possible to represent the set of roads which will become free as a simple path between some cities x and y. Your task is to help the government.
The first line contains two integers n and k (1 ≤ k < n ≤ 5000), the number of cities in Flatland and the maximum number of roads to become toll-free, respectively. Each of the next n - 1 lines contains two integers ui and vi, meaning that there is a road connecting cities ui and vi (0 ≤ ui, vi < n).
On the first line of the output, print one integer: the minimum of the most expensive simple path in Flatland that the government can achieve (
). On the second line, print the minimum number of roads t that must be made free to achieve that (0 ≤ t ≤ k). If t > 0, print two space-separated integers on the third line: the numbers of cities x and y such that all roads on the simple path between them must be made free (0 ≤ x, y < n, the simple path between x and y must contain exactly t roads).
8 3
0 2
0 5
2 3
5 1
4 5
5 6
6 7
2
3
2 6
5 2
0 1
0 2
0 3
0 4
2
0