J. Tetrees (Part 2)
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three integers $$$n$$$, $$$m$$$, and $$$k$$$. Your goal is to construct a not necessarily connected simple undirected graph with $$$n$$$ nodes and $$$m$$$ edges (which can be colored red, green, and blue) such that the score is at least $$$k$$$.

A "tetree" is defined as a selection of three edges such that they form a connected graph and connects 4 nodes and the three edges have different colors.

A "rainbow triangle" is defined as a cycle of length $$$3$$$ where each color is used exactly once.

The score of a graph is determined by the formula $$$$$$T - PR$$$$$$

where $$$T$$$ is the number of tetrees, $$$R$$$ is the number of rainbow triangles, and $$$P$$$ is an arbitrary number given in the input.

Input

The first line contains the test number $$$T$$$ $$$(1 \leq T \leq 10)$$$.

The second line contains $$$4$$$ integers: $$$n,m,k,P$$$.

Output

Output $$$m$$$ lines, the $$$i$$$-th line containing three integers $$$u_i,v_i,c_i$$$, representing the two nodes and the color of the edge. In particular, $$$c_i = 0$$$ for a red edge, $$$c_i = 1$$$ for a green edge, and $$$c_i = 2$$$ for a blue edge. The resulting graph should be a simple graph with a score of at least $$$k$$$.

Scoring

Test No.$$$\boldsymbol{n}$$$$$$\boldsymbol{m}$$$$$$\boldsymbol{k}$$$$$$\boldsymbol{P}$$$
$$$1$$$$$$4$$$$$$6$$$$$$7$$$$$$0$$$
$$$2$$$$$$6$$$$$$9$$$$$$24$$$$$$0$$$
$$$3$$$$$$100$$$$$$99$$$$$$35{,}937$$$$$$0$$$
$$$4$$$$$$100$$$$$$197$$$$$$80{,}000$$$$$$0$$$
$$$5$$$$$$100$$$$$$2{,}500$$$$$$1{,}850{,}000$$$$$$10^5$$$
$$$6$$$$$$100$$$$$$2{,}501$$$$$$1{,}852{,}000$$$$$$10^5$$$
$$$7$$$$$$100$$$$$$3{,}333$$$$$$4{,}300{,}000$$$$$$10^5$$$
$$$8$$$$$$15$$$$$$105$$$$$$4{,}000$$$$$$10^5$$$
$$$9$$$$$$100$$$$$$4{,}950$$$$$$12{,}000{,}000$$$$$$10^5$$$
$$$10$$$$$$300$$$$$$44{,}850$$$$$$1{,}000{,}000{,}000$$$$$$10^9$$$

Example
Input
0
4 3 1 0
Output
1 2 0
2 3 1
3 4 2
Note

The sample case is just for demonstrating the input and output format, and not an actual test that counts towards the score.