You are the manager of new basketball league. Your task is create schedule of games for this year.

League consists of n teams. Each team represents its home city. Each city i is placed at \((x_i, y_i)\) and has population of \(p_i\).

Each pair of teams i and j (\(i \neq j\)) has to play two games in any order: one of the games has to be played at home city of team i and the other one — at home city of team j.

You can choose any duration of the championship in days. Each day every team has to live in one of the given cities (this city is home city for some team). Plus each team can make at most one direct flight to another city every day.

For any team the cost of living at city i is \(A \cdot \sqrt{p_i}\) per day.

For any team the cost of direct flight from city i to city j is \(B \cdot \frac{\sqrt{(x_i - x_j)^2+(y_i-y_j)^2}} {\sqrt{p_i \cdot p_j}} \).

Before the first day of the championship each team is located in its home city.

At the end of the championship each team can be located anywhere.

There is one more restriction, that difference between two consecutive games of a single team has to be at least k. For example, if \(k = 1\) then a team can play its games every day.

Your salary depends of the championship costs. So you want to minimize costs as much as possible. Find the best schedule you can.

Input format

The first line of input contains integers n and k (\(1 \leq n \leq 150\), \(1 \leq k \leq 5\)).

The second line of input contains integers A, B (\(1 \leq A, B \leq 10^3\)).

Then follow n lines. The i-th of them contains integers \(x_i\), \(y_i\) and \(p_i\) (\(0 \leq x_i, y_i \leq 10^5\), \(1 \leq p_i \leq 10^5\)).

Output format

First line of output should contain integers l and q — the duration of championship, number of actions in championship.

l should be at most \(10^9\).

q should be at most \(250000\).

Then follow q lines.

The i-th of these lines contains integers d, t, a, b (\(1 \leq d \leq l\), \(1 \leq t \leq 2\), \(1 \leq a, b \leq n\)).

On \(t=1\) action means that on day d team a took a flight to the city b.

On \(t=2\) action means that on day d team a played with team b in the city where they were located on day d. Note that the city can be one of a or b.

Actions have to be printed in chronological order.

Scoring

Define your costs as C in certain test case. So you score for this test will be \(10^5 \cdot \log(C)\).

Now test set contains 50 tests with n = 150. After contest we will add 50 tests more and rejudge all solutions.

Please, see comments below. They contains more informations about tests.