The "Nondeterministic Machine" is a hypothetical computer that can execute an arbitrary number of instruction sequences simultaneously. This computer allows a new type of branch instruction; when this instruction is executed, the program splits into two, and both branches are executed concurrently.

A magical feature of the "Nondeterministic Machine" is program inversion. Given a program and its output, it can obtain an input that produces that output with the same time and space cost. This problem asks you to invert the execution of a program.

In this problem, you are given a pre-compiled program prog that contains several algorithms. Its input is a directed graph $G$ and an algorithm ID $k$, and its output is the result of running algorithm $k$ on the directed graph $G$. You are also provided with 10 output files generated by the program prog. Your task is to provide a possible input file for each output file.

To distinguish between them, in the following text, unless otherwise specified, we refer to the output file of the given program prog as the "input," and the input file for the program prog that you need to submit as the "output."

Input

This is an open-ended problem. All input data nm1.in~nm10.in are already in the problem directory. The first line of the input contains three positive integers $n, k, p$, representing the number of vertices in the graph $G$, the algorithm currently in use, and a scoring parameter calculated from the graph $G$.

The following lines contain several integers, the meaning of which you need to explore.

Output

For the 10 given input files nm1.in~nm10.in, you need to submit your output files nm1.out~nm10.out respectively.

The first line of the output file contains 3 integers $n, m, k$, representing the number of vertices, the number of edges, and the algorithm currently in use for the directed graph $G$.

The following $m$ lines each contain 3 integers $u, v, w$, representing a directed edge from node $u$ to node $v$ with weight $w$. The nodes are numbered from 1 to $n$. It is required that $w$ must be a non-negative integer not exceeding 20000, and no multiple edges are allowed. Self-loops are permitted.

Implementation Details

First, switch to the problem directory in the terminal: cd nm

The program prog is already in the problem directory. Its usage is: ./prog <output_file>

The program will take <output_file> as the input for prog and output the execution result to standard output. For example: ./prog nm4.out

The program will take nm4.out as the input for prog. If your file is invalid, the program will output an error message.

Examples

Input 1

3 0 0
0 0 1
1 0 0
0 1 0

Output 1

3 3 0
1 3 92
2 1 12
3 2 29

Note

In the example, the edge weight $w$ does not affect the execution result. You should also be aware that this may be the case in the actual data.

Subtasks

Each test case is scored independently.

• If the $n, k$ obtained after running your output are consistent with the input file, you get 1 point.
• If the $n, k, p$ obtained after running your output are consistent with the input file, you get 2 points.
• If the integers obtained after running your output are consistent with the input file, except for $p$, you get 4 points.
• During evaluation, each test case has a scoring parameter $s$. If the integers obtained after running your output are consistent with the input file, except for $p$, and the absolute difference between your $p$ value and the standard file's $p$ value does not exceed $s$, you get 7 points.
• If the integers obtained after running your output are completely consistent with the input file, you get 10 points.

If multiple conditions are met, the highest score is taken.

The $s$ values for each test case are as follows:

Interaction

The program prog also has a testing function that can provide a score or error message based on your input/output files and the $s$ value. The specific usage is: ./prog <output_file> <input_file> <s>

For example, to test test case 6, you can use: ./prog nm6.out nm6.in 8

Note

Most of the $k$ values in the problem consist of two digits. If the first digit of two algorithms $k$ is the same, it means these two algorithms use the same basic algorithm.

Please keep the input files nm*.in and your output files nm*.out safe and back them up in time to avoid accidental deletion.