Problem A. Age recognition ≡

Statement

A software development company named "Adnor" is starting a new challenging project: a video analytic application capable of classifying some features of people from images of their faces. One of such features is the age of the person. Since the problem of precise age recognition is still open and very difficult, for now the company will solve a slightly easier one: the system must determine an age interval to which the owner of presented face belongs.

Age interval is defined by minimum and maximum age, for example:

Most modern automatic classification methods are comprised of two steps: learning from a set of training samples, and classification itself.

For the training set, "Adnor" company has a database of face images with the exact age of each presented person. The training set is split into subsets according to desired age intervals and fed to the learning algorithm.

Sales division determined that the classifier should be able to distinguish between M age intervals. There is some freedom in choosing interval bounds, but for the optimal recognition quality training subset sizes should not differ too much. Strictly speaking, an entropy, measured in nats of sizes of these subsets should not be less than some constant E. Here entropy is defined as:

 − (1 / S) × ∑s_iln(s_i / S), where s_i is a subset size, and S — the sum of all subset sizes.

If this condition is not satisfied, some images should be excluded from one or more subsets to make their sizes closer and hence rise the entropy. Still, the training data should not be wasted, so some splitting must be found which uses as many samples as possible while having an entropy above or equal to E. Your task is to write a program which would find such an optimal splitting.

Input file format

Input file contains integers N M — maximum age in face images database and number of age intervals, followed by floating point number E — the lowest acceptable entropy value.

Following are N integers a₁.. a_N, where a_i is the number of available samples for age of i years.

It is guaranteed that at least one solution exists.

Output file format

Output file should contain M triplets of integer numbers l_i r_i s_i, each one corresponding to one age interval. l_i is lower age bound, r_i is upper age bound and s_i is the number of samples that should be used in the training subset for the ith interval. Intervals should be sorted in ascending order of their lower bounds. They should not overlap and must have nonempty training subsets (s_i > 0). If there is more than one solution, output any of them.

Constraints

1 ≤ N ≤ 100; 1 ≤ M ≤ 10; 0 ≤ a_i ≤ 10; 0 ≤ E ≤ 100;

There are no more than 50 non-zero values of a_i.

Sample tests

10 2 0.1
5 8 4 4 3 8 9 5 3 4

1 5 24
6 10 29

10 2 0.693
5 8 4 4 3 8 9 5 3 4

1 5 24
6 10 24