You must first choose an integer (). Then you must output the chosen and a tree on vertices satisfying the following conditions:
The vertices are numbered .
Each edge of has an integer weight between and , inclusive.
Phase 2
You are given an integer , followed by integers . For each (), you must express as the sum of the weights of at most 5 paths in .
Formally, for each you must output:
an integer (),
and pairs of vertices ,
such that
where denotes the weight of the path between vertices and in .
The weight of a path is defined as the sum of the weights of the edges contained in the path.
Interaction
The interaction proceeds as follows:
Phase 1
Choose an integer and a weighted tree , and output them in the following format:
Each triple represents an edge between vertices and with weight . The following conditions must hold:
Phase 2
First, an integer () is given. Then, integers () are given one by one. For each integer , you must output your answer in the following format:
Here () is the number of paths, and each pair represents a path between vertices and .
Note that the value () is provided only after the answer for has been printed.
Notes on Interactive Judging
The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely. Terminate the program immediately after printing the answer, or the verdict will be indeterminate. As some environments require flushing the output buffers, make sure that your outputs are actually sent. Otherwise, your outputs will never reach the judge.
