You are required to go from a point \((x_s, y_s)\) to \((x_f, y_f)\). You are getting tired at the rate of \(c_0\) per meter while you are walking. There is a rectangular canopy that is available on the way that reduces the exhaustion of energy. The \(i^{th}\) canopy is installed from point \((x1[i], y1[i])\) to \((x2[i], y2[i])\). The rate at which you are getting tired when you are under the canopy is \(c_i\) per meter.

If you are changing your direction of movement, then you become \(d\) unit tired. Your task is to minimize the value of your tiredness.

Input format

First line: Two space-separated integers \(n\) \((1≤n≤100\ 000)\) and \(d\) \((1≤d≤100)\)
Second line: Five space-separated integers, \(x_s\ y_s\ x_f\ y_f\ c_0\)
Next \(n\) lines: Five space-separated integers, \(x1[i]\ y1[i]\ x2[i]\ y2[i]\ c[i]\)

Note: It is guaranteed all coordinates are in the range \([1, 10^7]\) and \(1\le c[i] \le c_0 \le 10^9\).

Output format

The format of the output is as follows:

First line: Print \(m\) that denotes the number of partitions of your path \((1 \le m \le 10^5)\).
Next \(m\) lines: Print information about that partition \(from\_x_i\ from\_y_i\ to\_x_i\ to\_y_i\ through_i \) in each line.

Note

Here, \(through_i\) denotes the index of the canopy under which you are walking or \(0\) if you are walking without the canopy.
Your score will be calculated automatically by the explained path.