Problem G. Group performance ≡

Statement

Multi-vehicle cooperation is a hot topic in contemporary underwater robotics. Often a group of vehicles can finish the mission faster than just one. But you have to implement sophisticated control techniques to benefit from the cooperation.

Consider N vehicles and M tasks they should accomplish. Each task should be accomplished by exactly one vehicle. Each task is a track that a vehicle should follow. The task number i is defined by two edge points a_i and b_i, and length d_i (d_i ≥ |a_i − b_i|).

Vehicle is allowed to follow a track in any direction — either from a_i to b_i or from b_i to a_i. In both cases the length of the path will be d_i.

A plan is a sequence of tasks for each vehicle in order of execution. Every task in the plan is followed either in direct order (a to b) or in reverse order (from b to a). Each task should appear exactly once in the whole plan.

The j-th vehicle has a starting point s_j. Vehicle executes its tasks according to its part of a plan. When a vehicle accomplishes one task, it goes to the start point of the next one, moving along the straight line. When all tasks assigned to a vehicle are done, it stops. Vehicle path length is a total path traveled by the vehicle during the plan execution. Plan length is a maximal vehicle path length of all vehicles in the plan.

Your program must, given vehicles and tasks, find a plan of minimal length.

Assume that vehicles operate on a plane (plane of constant depth) and that the vehicle size may be ignored.

Input file format

Each point in the input file is described with two integers — its x and y coordinates.

On the first line of input file there are integers N M. Following N lines describe starting points s_i.

Next M lines describe tasks, each task descriptions consisting of points a_i, b_i and path length d_i.

Output file format

Output file must describe a plan of minimal length. If there several such plans, output any of them.

Plan description consists of N blocks, each describes a sequence of tasks for one vehicle. j − th block starts with non-negative integer num_j, followed by num_j pairs (t_jk, dir_jk). Here t_jk denotes a number of k-th task for j-th vehicle, it is an integer in range 1..M. The dir_jk is either 0 or 1: 0 stands for passing t_jk from a to b, 1 stands for passing t_jk from b to a.

Constraints

1 ≤ N, M ≤ 10; 0 ≤ d_i ≤ 10⁴;

All coordinates are integers in range 0..10³.

Sample tests

3 4
2 8
2 5
2 2
5 2  12 2  14
14 7  12 9  3
12 4  5 6  14
5 7  10 8  10

2 4 0 2 1
1 3 1
1 1 0