On August 15, 2008, the rowers from Nizhny Tagil Mikhail Kuznetsov and Dmitry Larionov won a bronze Olympic medal in the men's slalom canoe double event.
After that, the regional administration decided to support the Canoe Slalom School “Polyus” in Nizhny Tagil, where the athletes had trained. There were n young canoeists training at the school at that time. The principal of the school reported that m crews of tandem canoes had won national competitions in the years preceding the Olympics. Some of the athletes had won more than once as members of different crews. The principal asked the administration to pay the athletes bonuses so that the total bonus of each of the winning crews would be at least k roubles.
However, because of the financial crisis, officials from the Ministry for Physical Education and Sport tried to spend as little money as possible for granting the principal's wish. What bonuses were paid to the young athletes?
Input
The first line contains the integers n, k, and m (2 ≤ n ≤ 500;
1 ≤ k ≤ 10000; 0 ≤ m ≤ 100000). In each of the following m lines you are given two different integers separated with a space. These are the numbers of athletes from one of the winning crews. The students of the school are numbered from 1 to n. Each winning crew enters the list only once.
Output
Output in the ith line the amount of the bonus paid to the ith athlete with an absolute error of at most 10^{−6}.
If there are several answers, output any of them.
Sample
input  output 

4 1000 4
1 2
1 3
2 4
3 4
 146.5
853.5
853.5
146.5

Problem Author: Alexander Ipatov (prepared by Eugene Kurpilyanskiy)
Problem Source: Ural Championship 2011