Chef's Ingredient Allocation

A chef wants to prepare (m) dishes for children using exactly (k) grams of ingredients per dish. The chef has purchased (n) types of ingredients with masses (d_1, d_2, \ldots, d_n) (in grams) such that (\sum_{i=1}^n d_i = m \times k). All values (d_i) and (k) are positive integers. When making each dish, at most two types of ingredients can be used and if two are used then the contribution from each ingredient in that dish must be a positive integer and the total equals (k) grams. In other words, the chef needs to partition the ingredients among (m) dishes such that for each dish:

• The dish uses either one or two types of ingredients.
• If one type is used then that ingredient contributes exactly (k) grams.
• If two ingredients are used then one ingredient contributes (x) grams and the other contributes (k-x) grams (with (1 \le x < k)).

Moreover, all the purchased ingredient amounts must be used exactly. Your task is to decide whether a valid allocation exists, and if so, output one such allocation.

The output format for a valid allocation is as follows:

• Print a line with the string “YES”.

• Then, for each dish from (1) to (m), print a line describing the dish. For a dish that uses one ingredient, output:

  1 ingredient_index amount

  For a dish that uses two ingredients, output:

  2 ingredient_index1 amount1 ingredient_index2 amount2

Note that ingredient indices are 1-indexed and the dishes must be output in order. If no valid allocation exists, simply output a single line with “NO".

inputFormat

The input begins with a line containing three positive integers (n), (m), and (k) --- the number of ingredients, the number of dishes, and the grams required for each dish respectively. The next line contains (n) positive integers (d_1, d_2, \ldots, d_n), where (d_i) represents the mass (in grams) of the (i)-th ingredient. It is guaranteed that (\sum_{i=1}^n d_i = m \times k).

outputFormat

If a valid allocation exists, output “YES” on the first line. Then output exactly (m) lines, one for each dish. For each dish, if only one ingredient is used, output:

1 ingredient_index amount

If two ingredients are used, output:

2 ingredient_index1 amount1 ingredient_index2 amount2

(Note: ingredient indices are 1-indexed.)

If no valid allocation exists, output a single line with “NO”.

sample

3 2 5
5 3 2

YES
1 1 5
2 2 3 3 2

</p>