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.