Problem Background

「{!@@(*@@￥';l]dw@)%)%&^_^}（可恶的人类！我一定会回来的！）」

It has pushed its spacecraft to its maximum speed, attempting to escape this hell filled with humans.

……

Problem Description

After so many years, the alien's spacecraft speed is no longer a match for Earth's spacecraft. Therefore, it has decided to use warp points to escape.

On a planar map, there are $n$ warp points with coordinates $(x_i, y_i)$. Some of these warp points are connected by bidirectional space tunnels, totaling $m$ tunnels. Each tunnel connects warp points $u_i$ and $v_i$, and activating this tunnel requires $w_i$ units of energy. Note that to ensure the space tunnels do not interfere with each other, for any two space tunnels $\bm{i,j}$, the line segments connecting points $\bm{u_i,v_i}$ and points $\bm{u_j,v_j}$ do not intersect. It is guaranteed that there are no two space tunnels with the same start and end points.

The alien's technology is quite miraculous. To successfully warp away, the alien must pass through all warp points at least once. It can start warping from any point and end at any point. The total energy spent by the alien is the bitwise OR sum of the energies required to activate all the tunnels on the path. Activating the same tunnel more than once only requires activating it once.

The alien's spacecraft has $x$ units of energy, so the total energy spent on the chosen warp plan must not exceed $x$. To intercept the alien, local forces can perform the following operations any number of times:

• Select a bidirectional tunnel connecting $u$ and $v$ (you need to ensure there is a bidirectional tunnel between points $u$ and $v$);
• Increase the energy required to activate it by $w$ ($w \ge 0$ and the energy required after the operation must not exceed $2^{31} - 1$).

Where $u, v, w$ can be specified freely. The cost of each operation is the number of ones in the binary representation of $w$. (i.e., the __builtin_popcount() function in C++)

To atone, you need to design an operation scheme that prevents the alien from warping away and minimizes the cost of this scheme.

Input Format

Read data from standard input.

The first line contains one positive integer $W$, representing the scoring parameter for this test case.

The second line contains three integers $n, m, x$, representing the number of warp points, the number of bidirectional tunnels, and the energy available on the alien's spacecraft, respectively.

Lines $3$ to $(n+2)$, the $(i+2)$-th line contains two integers $x_i, y_i$, representing the coordinates of the $i$-th warp point.

The next $m$ lines, each containing three integers $u_i, v_i, w_i$, represent the two warp points connected by each bidirectional tunnel and the energy required to activate it.

Output Format

Output to standard output.

This problem uses a custom judge (special judge).

The first line of the output should contain a non-negative integer $k$, representing the total number of operations.

The next $k$ lines, each containing one operation in the form $u~v~w$, represent increasing the energy required to activate the bidirectional tunnel connecting $u$ and $v$ by $w$.

You need to ensure $0 \le k \le 10000$, otherwise, it will be considered an invalid answer.

Sample Input and Output

Sample Input #1

1
5 6 9
0 1
0 0
0 -1
-1 0
1 0
1 2 10
1 4 1
2 3 8
3 4 5
3 5 1
1 5 1

Sample Output #1

1
2 3 2

Sample Input #2

See attached file intercept2.in

Sample Output #2

See attached file intercept2.ans

Sample Input #3

See attached file intercept3.in

Sample Output #3

See attached file intercept3.ans

Notes/Hints

[Sample Explanation]
+ Sample 1 Explanation:
After the operation, the planar map looks like this (omitting the coordinate axes):

Since the activation energy required for the space tunnels connected to warp point 2 is all 10, the minimum energy required for successful warping is at least 10, so the alien cannot warp away. The cost is 1, and clearly, there is no operation scheme with a lower cost.

[Scoring Method]

For each test case, if your operation scheme is invalid or allows the alien to successfully warp away, you will receive 0 points for that test case.

Otherwise, let the scoring parameter for the test case be $W$, the standard answer's cost be $a$, and your operation scheme's cost be $b$. Your score $s$ will be given by the following formula:

$$ s = \max\left(1 - \frac{b - a}{a} \times W, 0\right) \times 10 $$

[Data Range]

For $100\%$ of the data, $12 \le n \le 53280$, $n - 1 \le m \le 3n - 6$, $0 \le x < 2^{31} - 1$, $0 \le |x_i|, |y_i| \le 3 \times 10^4$, $0 \le w_i < 2^{31}$, $1 \le W \le 1000$.

[Checker]

For convenience in testing, we have provided the checker.cpp file in the intercept directory. You can compile this file and use it to verify your output files. Note that it is not identical to the checker used in the final evaluation, and you should not be concerned with its specific code.

Compile command:

g++ checker.cpp -o checker -std=c++14

Usage:

./checker <inputfile> <outputfile> <answerfile>

The checker may return one of the following states:

• accepted: Indicates your output is completely correct.
• points x: Indicates your output is partially correct and you can receive a proportion of $x$ of the points for this test case.
• wrong answer: Indicates you receive 0 points for this test case.

For all non-accepted states, the checker will output one of the following messages:

• A: Indicates your output is invalid.
• B x y: Indicates the cost of your output scheme is $x$ and the standard answer is $y$.
• C: Indicates your output scheme allows the alien to successfully warp away.

[Postscript]

He knew he would never return home. He still remembered the commander's final words before reversing time. He had spent almost half his life establishing a new base and reorganizing the army. His purpose was to prevent this from happening again. Now, the base was destroyed, and he was trapped in this dark and lifeless galaxy. He finally realized that everything was predetermined.

「Commander, I'm sorry.」

「The cabin will self-destruct in ten seconds. Ten. Nine. Eight. Seven...」

Raising the pistol, aiming at his temple.

「Six. Five. Four. Three...」

With a bang, he collapsed, his eyes lifeless.

「Two. One.」

After the loud explosion, no one will be remembered.

见题面 Input 部分

见题面 Output 部分