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?

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 in the i-th line the amount of the bonus paid to the i-th athlete with an absolute error of at most 10⁻⁶. If there are several answers, output any of them.