N Ricks from different universes gathered in a restaurant to celebrate Rick's Birthday. The restaurant accepts only pizzcoins in cash, but some of the Ricks had no enough cash to pay.
More precisely, i-th Rick ordered food for Ai pizzcoins, paid Bi pizzcoins in cash, and together they paid exactly the amount of the check.
After the party Ricks want to pay off each other. Every Rick has infinite amount of pizzcoins in his bank account and may transfer pizzcoins to the others Ricks.
Find any list of transfers satisfying following conditions:
no one owes pizzcoins in the end. That is, after paying the check in the restaurant and all transfers, every Rick spent exactly what he spent in the restaurant;
the number of transfers doesn't exceed N;
the total amount of transfered pizzcoins doesn't exceed doubled check amount.
The first line contains one integer N (2 ≤ N ≤ 1000), denoting the number of Ricks.
The second line contains N integers Ai (0 ≤ Ai ≤ 106), denoting the price of food in pizzcoins ordered by i-th Rick.
The third line contains N integers Bi (0 ≤ Bi ≤ 106), denoting the amount of pizzcoins were paid by i-th Rick in cash.
It is guaranteed that 
.
Display the list of pizzcoin transfers. Every transfer should be displayed in a seperate line, and should contains the following format: "F T S", where F is a number of Rick who makes transfer, T is a number of Rick who receives pizzcoins, S is the number of transfered pizzcoins (1 ≤ F, T ≤ N; 0 ≤ S ≤ 2 × 109).
It is guaranteed that the list will contain at least one item. You can choose any solution that satisfies the constraints.
6
100 200 50 150 400 150
50 500 0 150 100 250
1 2 50
3 2 50
5 2 200
5 6 100
2
0 1000000
1000000 0
2 1 1000000
To protect the forest from poachers, it was decided to surround all the trees with barbed wire.
When purchasing materials for the fence, an error was made, and now you have an unlimited supply of wire and only one pillar.
Barbed wire can be stretched between two trees or a tree and a pillar only in a straight line. If a tree touches a barbed wire, its bark is damaged.
Determine the minimum number of trees have to be damaged provided that all trees must be inside closed barbed wire fence, and the pillar can be placed in any free point of the plane.
The first line contains one integer N (3 ≤ N ≤ 105).
The folling N lines contains two integers Xi, Yi, denoting coordinates of i-th tree ( - 106 ≤ Xi, Yi ≤ 106). Each tree has unique coordinates.
Display the minimum number of trees with damaged bark.
3
0 0
4 2
2 1
3
5
0 1
-5 -2
4 0
2 -2
4 -4
2
The one of possible solutions for the second sample is shown below (damaged trees are marked as crosses, the pillar is a circle, barbed wire is a dashed line):
You are playing a computer game, where you must successively cast N spells (some of them may be repeated).
There are K keys on the keyboard that can be used to assign spells.
During the game, you may assign different spells to the same key. But at the moment of pressing the key, the last assigned to this key spell will be casted.
Determine the minimum number of spell assignments that will be necessary to complete the game. Initially no spells are assigned to any key.
The first line contains two integers N (1 ≤ N ≤ 105) and K (1 ≤ K ≤ 105), denoting the number of spells and the number of keys correspondingly.
The second line contains N numbers Ai (1 ≤ Ai ≤ N), denoting the spell numbers in the order in which they must be casted to complete the game.
Display the minimum total number of spell assignments to a key.
5 2
1 3 1 2 3
3
5 1
1 1 2 2 2
2
8 3
1 2 3 1 2 3 1 3
3
Let's consider the first example. First, the player can assign the spell 1 to the first key and press it. Then he can assign the spell 3 to the second key and press it. Then, without performing any new assignments, he simply presses the first key. Then it is advantageous for him to assign the spell 2 to the first key and press it, and in the end he just presses the second key.
Scotland Yard did not cope with the investigation of the series of murders, so Sherlock Holmes was called to the rescue.
After collecting the evidence on the crime scene, the great detective understood that all the murders were committed by one person, and all the dead were familiar with him.
Holmes knows all the pairs of people who were familiar with each other before the first murder was committed. He also knows that all the people who familiar with dead, including the murderer, come to his funeral and met there with each other (after that all these people will be familiar with each other). It is also known that the killer did not commit new murders until the end of the funeral of his previous victim.
Determine whether Sherlock Holmes has enough information to uniquely identify the killer, and the day after which a series of crimes could be stopped by arresting him.
The first line contains two integers N (2 ≤ N ≤ 105) and M (1 ≤ M ≤ min(2 × 105, N × (N - 1) / 2)), denoting the number of people and the number of familiarity relationships.
The next M lines contain two integers Ui and Vi (1 ≤ Ui, Vi ≤ N, Ui ≠ Vi), denoting person Ui and Vi were familiar before the first murder. Familiarity relationships are unique.
The next line contains one integer T (1 ≤ T ≤ N - 1), denoting the number of days.
The last line contains T number Ai, denoting a number of died person on i-th day.
Display two numbers: the number of the day after which you can uniquely identify the killer and his identifier. The days and IDs of people are numbered from 1.
If you can not identify the killer, display - 1.
4 3
1 2
1 3
4 3
2
1 4
2 3
5 4
1 2
3 1
1 4
5 4
3
1 4 5
-1
6 6
1 2
2 3
3 4
4 5
5 2
2 6
4
2 4 6 5
4 3
N students in the class room are seated in a row. Let a number of the variant of the test for i-th student is Ai (1 ≤ i ≤ N).
To prevent writing off from each other, the numbers of test variant for all adjacent students should be different. Formaly the following condition must be fulfilled: Ai ≠ Ai - 1 for all i > 1.
The quality control of education at the institute is testing. When the examiner enters the audience, he writes out the variants of each K-th student, starting with certain student, which is unknown. A check is considered successful if all written variants are different. Thus, in order to be guaranteed to pass the test, it is necessary to satisfy the condition Ai ≠ Aj for all 
.
Help the professor to find such a distribution of test variants from 1 to V among N students, where they can not write off from each other, the quality control of education will be successfully passed and the number V will be the lowest possible.
The first ans only line containts two integers N and K (1 ≤ K ≤ N ≤ 105).
Dispaly N numbers: the distribution of numbers of test variants among all students, according to above conditions. If there are several possible answers, choose any.
4 3
1 2 1 2
5 2
3 1 2 3 1
3 1
1 2 3
N Unidentified Flying Saucers has arrived in "MK Ultra" spaceport. To identify saucers, they must first be washed. All saucers are arranged in the stack in particular order. The height of the i-th saucer from the top of the stack is Hi.
There are two washing machines in the spaceport. It is allowed to load several consequent saucers from the top of the stack to a washing machine if and only if this washing machine is free. The height of the buffer of the first washing machine is D1, and the height of the buffer of the second one is D2. It is impossible to load saucers in the buffer with a total height greater than the height of the corresponding buffer. If at some point of time both machines are free, they can perform loading in any order, but each loading operation should be atomic.
While there are flying saucers in the washing machine buffer, it pulls out and wash them one at a time. While all saucers from the buffer are not washed, the machine is considered busy. Washed saucers are sent for identification and are not involved in the washing process any more. The first machine washes saucer with height Hi for S1 × Hi seconds, and the second one washes it for S2 × Hi seconds.
Determine the minimum period of time needed to wash all flying saucers. The time for all processes except for directly washing saucers by wasing machines can be neglected. If necessary, the machines can stand idle for a while, if this minimizes the final result.
The first line contains two integers S1 and S2 (1 ≤ S1, S2 ≤ 50).
The second line contains two integers D1 and D2 (1 ≤ D1, D2 ≤ 10000). It is guaranteed that any saucer can be washed in any washing machine.
The third line contains the number of flying saucers in the initial stack N (1 ≤ N ≤ 200).
The last line contains N integers Hi (1 ≤ Hi ≤ 50), denoting the heights of the saucers, starting from the top of the stack.
Print single integer: the minimum number of seconds from the beginning of the washing until the moment when all flying saucers are sent for identification.
4 3
14 11
10
1 2 3 9 5 2 7 3 2 8
72
In the example, the minimum time could be achieved as follows:
- at time 0 the first machine loads saucer 1, the second loads 2;
- at time 4 the first machine loads saucer 3;
- at time 6, the second machine loads saucer 4;
- at the time 16 the first machine loads saucers 5 - 7;
- at time 33 the second machine loads saucers 8 - 9;
- at time 48, the second machine loads saucer 10.
Every second the task distributor receives a new task. Tasks are numbered sequentially, starting from zero.
If the task number is not divided into K, then its execution on any server takes T seconds, otherwise it takes 2 × T seconds.
After receiving the task, the distributor immediately transfers it to one of the free servers. If there are no free servers at the time of the task's receipt, then a collapse occurs.
Initially, all servers are free. The server executing the task becomes free immediately when the task execution is finished.
What is the minimum number of servers needed to ensure that the collapse never occurs?
The first and only line contains two integers T (1 ≤ T ≤ 1018) and K (1 ≤ K ≤ 1018).
Display the minimum number of servers needed to ensure that the collapse never occurs.
4 3
6
3 4
4
2 2
3
1 2
2
There are N questions in the intellectual game. The correct answer for the i-th question is i. For each question, the deadline of answers reception Ti is known.
The player on the smartphone's screen in the game entered into the text field M numbers Bi. For each of them the time on the smartphone Si is known. Initially, the field is empty. Input new value doesn't not take time, replaces the previous value, and the field is never cleared anymore.
The system considers the player's answer to the i-th question only the number that was entered last by the time Ti, inclusive.
You are given Q queries consisting of one number Di, denoting the difference to add to the time of all the replies from the player when calculating its result.
For each query, determine how many correct answers the player gave.
The first line contains one integer, denoting the number of questions N (1 ≤ N ≤ 105).
The second line contains N numbers Ti (1 ≤ Ti ≤ 109), denoting the deadline for receiving responses to questions, arranged in ascending order.
The third line contains one integer M (1 ≤ M ≤ 105), denoting the number of entered numbers.
The next M lines containing two integers Si (1 ≤ Si ≤ 109) and Bi (1 ≤ Bi ≤ 105), denoting the time on the smartphone at the moment of input and the entered number correspondingly. Si > Si - 1 for all i > 1.
The next line contains one integer, dinoting the number of queries Q (1 ≤ Q ≤ 105).
The last line contains Q integers, denoting the query with parameter Di ( - 109 ≤ Di ≤ 109).
Display Q integers: answers to queries in the order of the queries in the input.
3
10 13 20
6
7 5
8 1
11 2
12 3
13 2
15 3
5
0 -20 1 10 -1
3 1 2 0 2
In the first query, time does not shift, and the correct answers are counted on all questions. In the second query, the player is only given the answer to the third question. In the third query, the player's answers to the 1st and 3rd questions are counted. In the fourth query, the player does not count any of the answers. In the fifth query the player counts the answers to the 2nd and 3rd questions.
The phone lock screen consists of 9 numbered dots arranged in three rows three pieces each.
The unlock key is a sequence of two or more non-repeating dots. The segments between adjacent dots in the unlock key can not pass through another dot. Thus, in the unlock keys, the following pairs of points can not be adjacent (in any order): {1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3, 9}, {1, 9}, {3, 7}.
On the phone screen between segments of the dots are visible segments with fingerprints, which means that such a pair of dots should be present in the unlock key, and they should be adjacent.
Determine how many unlock keys exist that satisfy the condition of the task. It is guaranteed that the answer will not be zero.
The first line contains the number of segments with traces from the finger N (0 ≤ N ≤ 8).
Each of the next N lines contains two integers Ai and Bi (1 ≤ Ai, Bi ≤ 9), denoting the i-th segment between two number dots.
Display one integer: the number of unlock keys.
6
1 8
8 7
7 5
4 5
2 4
2 6
6
4
3 5
5 2
2 6
6 1
110
Segments from first sample are shown at the picture. Suitable keys are: 1875426, 18754263, 18754269, 36245781, 6245781, 96245781.
The country of Doubland consists of two archipelagos, including N and M islands.
The islands inside the archipelagoes are connected by N - 1 and M - 1 bridges respectively.
It is possible to move on the bridges in both directions. Also it is possible to reach every island from every island of the archipelago, moving only on bridges. The time spent on the road will be equal to the number of bridges passed.
Doubland is a poor country. Therefore, when there is a threat of a major natural disaster, the government can only turn on alarming sirens simultaneously on all islands and hope that some of the residents will get a distress signal to the mainland.
The most reliable way to signal is the telegraph. Unfortunately, telegraphs have survived only on islands that are connected to their archipelago by exactly one bridge, and on each of the archipelagos only one Morse code specialist resides.
Determing the expect value of the minimum time, when at least one of the Morse code specialists reachs the telegraph, provided that each of them at the moment of triggering alarm sirens can be equally likely to be on any of the islands of its archipelago.
The first line contains one integer N (2 ≤ N ≤ 105), detonig the number of islands of the first archipelago.
The next line contains N - 1 lines that contain two integers Xi and Yi (1 ≤ Xi, Yi ≤ N), denoting the i-th bridge connects islands Xi and Yi of the first archipelago.
The next line contains one integer M (2 ≤ M ≤ 105), detonig the number of islands of the second archipelago.
The next line contains M - 1 lines that contain two integers Uj, Vj (1 ≤ Uj, Vj ≤ M), denoting the j-th bridge connects islands Uj and Vj of the second archipelago.
Display one real number: the expect value. The answer is correct if the absolute or relative error does not exceed 10 - 9.
4
1 2
1 3
3 4
3
1 2
1 3
0.166666666667
2
1 2
3
1 2
1 3
0.000000000000
A popular messenger will be blocked in X hours. Until this time Nikolay wants to send as many messages as possible to Pavel.
Nikolay writes one message A minutes, after which it is delivered B minutes. Nikolay can start to write a new message immediately after sending the previous one, but he will not send it until the previous one is delivered, even if he has enough time to finish it before.
Determine how many messages Pavel may receive before the messenger is blocked. If some message comes to Pavel at the time of blocking, it will be received successfully.
The first line contains one integer X, denoting the number of hours to the messenger blocking (1 ≤ X ≤ 24).
The second line contains two integers: A is the number of minutes required to write a message, and B is the number of minutes required to deliver a message (1 ≤ A, B ≤ 60).
Print single integer: the maximum number of messages that Pavel may receive.
2
10 20
5
3
20 10
8