A distant country has ~N~ cities in it. The elections were just held in this country, so the new prime minister was elected. Currently, there is not a single road in this country, so the prime minister decided to modernize the country by connecting some cities with two-way highways and form counties. Two cities will be located in the same county if it is possible to get to one city from the other using the newly built roads. Each city will be located in exactly one county. Each county consists of one or more cities.

The cities are represented as points in a two-dimensional coordinate system. The road between two cities is represented as a line segment connecting two points where the cities are located. The length of the road is equal to the length of the line segment in kilometers.

The country is currently suffering from recession, so the prime minister decided that, because of the lack of budget, they will not build roads longer than ~D~ kilometers. Additionally, the prime minister is happy about the small things, so he will be happy if, in at least one county, there exists a nonempty subset of cities (it can include all cities in the county) where the total sum of residents is divisible by ~K~. For instance, if ~K = 4~ and there is a county with cities that have ~3, 5, 7~ residents respectively, the prime minister will be happy because the sum of residents in the first two cities is equal to ~8~.

Help the prime minister in cutting the costs by determining the minimal ~D~ such that the prime minister can build roads and be happy about the small things at the same time.

Input Specification

The first line of input contains the integers ~N~ and ~K~ ~(1 \le N \le 50\,000, 1 \le K \le 30)~. Each of the following ~N~ lines contains three integers ~x_i~, ~y_i~, ~k_i~ ~(0 \le x_i, y_i, k_i \le 100\,000\,000)~, that represent the ~x~ coordinate of the city, the ~y~ coordinate and the number of residents in that city, respectively. There will not be two cities with the same coordinates in the input data. Additionally, there will not be a single city with the number of residents divisible by ~K~.

In test cases worth 40% of points the number of cities ~N~ will be less than or equal to ~1000~.

Output Specification

The first and only line of output must contain the minimal ~D~ such that it is possible to build roads with the condition that the prime minister is happy. Output ~D~ rounded to 3 decimal places. The input data will be such that there is always a solution.

Sample Input 1

3 3
0 4 4
1 5 1
2 6 1

Sample Output 1

1.414

Explanation for Sample Output 1

The only way to keep the prime minister happy is if all the cities are in the same county. The minimal ~D~ for which that is possible is 1.414.

Sample Input 2

6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10

Sample Output 2

5.657

Explanation for Sample Output 2

The prime minister will be happy if the first ~5~ cities are in the same county. If ~D = 5.657~, the prime minister can connect cities ~1, 2, 3, 5~ with city ~4~. In that case, the sum of residents in cities ~1, 2, 3, 4, 5~ will be ~11~, which is divisible by ~11~, so the prime minister will be happy.

Sample Input 3

6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3

Sample Output 3

2.000