<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

480. Gena's Soul Cakes
Time limit per test: 1 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



This story is about a boy, called Gena. He is quite a usual boy who goes to school, celebrates All Hallows Eve, also known as Halloween Day, and besides likes programming contests.


One Halloween Day he went from house to house begging for "soul cakes". He happened to collect many "soul cakes" of various tastes that day, and his happiness seemed have no limits. But his elder brother Roma, who was lazy and rude boy, demanded to give him ten cakes. Gena didn't loose control over the situation and gave his brother ten cakes of the same taste in order not to show that he had many tastes, because Roma could demand more cakes. Since that time Gena was thinking about that situation. And after Gena had learnt on Geometry classes about three-dimentional space figures, he invented the following problem.


Consider non-convex figure denoted as "corner" in three-dimentional space. It consists of four equal cubes. One of the cubes has a common face with each of the others. There is the only one point belonging to all four cubes, and this point coinsides one vertex of any cubes (see picture below). Every "corner" is charaterized by two values: color and an integer length of an edge of any cubes (denoted as "size"). "Size" is always equal to some power of two, so only index is given. The problem is to construct a big "corner" comprising given figures under the restiction of using as little number of different colors as possible given "size" of this big "corner". 


Input
The first line of input contains two space separated integers: c — the number of colors, and k — the index of power of two which is equal to "size" of big "corner" (1 ≤ c, k ≤ 1000). Next c lines contain k integers aij each. aij equals the number of "corners" with color i and "size" 2j. (0 ≤ aij ≤ 1000 for 1 ≤ i ≤ c, 0 ≤ j < k).

Output
The first line of output should contain integer n denoting the number of figure types used in constructing big "corner". Next n lines should contain ai, bi, ci denoting color, "size" and number of "corner" of such type respectively. Please, separate these numbers by single spaces. If there are multiple solutions, output any of them. Every type of "corner" should appear in output no more than once. If it is impossible to construct big "corner" even using all figures, print "NO SOLUTION" to output.

Example(s)
sample input
sample output
1 1
8
1
1 0 8

sample input
sample output
2 2
1 7
7 0
3
1 1 7
1 0 1
2 0 7

<|response|>
## 1. Abridged problem statement

We have `c` colors of 3D “corner” figures. A corner of size `2^j` consists of 4 cubes of edge `2^j`.

Given counts:

```text
a[i][j] = number of corners of color i and size 2^j
```

for `0 <= j < k`, we need to construct one big corner of size `2^k`.

The goal is to use the minimum possible number of different colors. If several constructions are possible, output any one. If construction is impossible even with all pieces, output:

```text
NO SOLUTION
```

Constraints:

```text
1 <= c, k <= 1000
0 <= a[i][j] <= 1000
```

---

## 2. Key observations needed to solve the problem

### Observation 1: Volume can be measured as powers of 8

A corner of size `2^j` consists of 4 cubes of edge `2^j`, so its volume is:

```text
4 * (2^j)^3 = 4 * 8^j
```

The factor `4` is common for all corners, so we can use a normalized volume:

```text
corner of size 2^j has weight 8^j
```

The big corner has size `2^k`, so its normalized volume is:

```text
8^k
```

---

### Observation 2: One corner can be split into 8 smaller corners

A corner of size `2^j` can be divided into exactly:

```text
8
```

corners of size `2^(j - 1)`.

Therefore, if we do not have a large corner, we may replace it by 8 smaller corners, recursively.

---

### Observation 3: Feasibility depends only on total volume

For a chosen set of colors `S`, construction is possible iff:

```text
sum over i in S, j of a[i][j] * 8^j >= 8^k
```

Why?

- Necessity is obvious: total available volume must be at least the big corner volume.
- Sufficiency follows from the recursive subdivision: missing larger corners can always be replaced by 8 smaller ones.

So for a set of colors, only its total normalized volume matters.

---

### Observation 4: To minimize colors, take colors with largest total volume

For each color compute:

```text
volume[i] = sum_j a[i][j] * 8^j
```

Since feasibility depends only on total volume, the best way to achieve enough volume with the fewest colors is:

1. Sort colors by decreasing `volume[i]`.
2. Take colors in that order.
3. Stop when the chosen colors can build the big corner.

The first feasible prefix gives the minimum possible number of colors.

---

### Observation 5: Values are huge

`k` can be up to `1000`, so `8^k` is enormous.

In C++, we cannot store these values in normal integers. We store each color volume as base-8 digits.

In Python, arbitrary precision integers are available, so we can store volumes directly.

---

## 3. Full solution approach based on the observations

### Step 1: Read input

Input gives `c`, `k`, and a `c x k` table:

```text
a[i][j]
```

where `i` is the color and `j` is the size index.

---

### Step 2: Compute total volume of every color

For each color:

```text
volume[i] = a[i][0] * 8^0 + a[i][1] * 8^1 + ... + a[i][k - 1] * 8^(k - 1)
```

In C++, store this as normalized base-8 digits.

Example:

```text
coefficients: [10, 2]
```

means:

```text
10 * 8^0 + 2 * 8^1
```

After carrying in base 8:

```text
10 = 2 + 1 * 8
```

so normalized digits become:

```text
[2, 3]
```

which means:

```text
2 * 8^0 + 3 * 8^1
```

---

### Step 3: Sort colors by decreasing volume

Sort color indices by their computed volumes.

---

### Step 4: Add colors greedily until feasible

Maintain:

```text
sum_caps[j] = total available pieces of size 2^j among chosen colors
```

After adding each color, test if the chosen colors can build the big corner.

---

### Step 5: Greedy feasibility test and count selection

To build a corner of size `2^k`, initially we need:

```text
8 corners of size 2^(k - 1)
```

Let:

```text
need = 8
```

Process sizes from largest to smallest:

For size `j`:

- If `sum_caps[j] >= need`, we use exactly `need` pieces of size `j`, and construction is complete.
- Otherwise, we use all `sum_caps[j]` pieces.
- The missing amount is:

```text
missing = need - sum_caps[j]
```

Each missing size-`j` corner must be replaced by 8 size-`(j - 1)` corners:

```text
need = missing * 8
```

If after size `0` we still have unmet demand, construction is impossible with the current chosen colors.

This greedy process also gives us:

```text
x[j] = number of pieces of size 2^j to actually use
```

---

### Step 6: Output actual pieces

Once we know how many pieces of each size are needed, distribute them among the chosen colors.

For every size `j`:

```text
need = x[j]
```

Iterate over chosen colors and take as many available pieces of size `j` as possible until `need = 0`.

Each output line is:

```text
color size_index count
```

Colors are output 1-indexed.

---

### Complexity

Let `c` be the number of colors and `k` the number of size levels.

Computing volumes:

```text
O(c * k)
```

Sorting colors:

```text
O(c log c * k)
```

in C++ because comparing base-8 digit vectors can take `O(k)`.

Greedy feasibility checks:

```text
O(c * k)
```

Total complexity:

```text
O(c * k + c log c * k)
```

This is fine for `c, k <= 1000`.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int c, k;

// a[i][j] = number of corners of color i and size 2^j
vector<vector<int>> a;

/*
    Normalize coefficients of powers of 8.

    Input:
        coeffs[j] means coeffs[j] * 8^j

    Since coeffs[j] may be greater than 7, we perform carries
    and return standard base-8 digits, least significant digit first.
*/
vector<int> normalize_base8(const vector<int>& coeffs) {
    vector<int> digits;
    digits.reserve(coeffs.size() + 5);

    long long carry = 0;

    for (int v : coeffs) {
        long long cur = v + carry;

        digits.push_back((int)(cur % 8));
        carry = cur / 8;
    }

    while (carry > 0) {
        digits.push_back((int)(carry % 8));
        carry /= 8;
    }

    // Remove leading zeroes
    while (!digits.empty() && digits.back() == 0) {
        digits.pop_back();
    }

    return digits;
}

/*
    Compare two base-8 numbers.

    Digits are stored least significant first.

    Returns:
        -1 if x < y
         0 if x == y
         1 if x > y
*/
int compare_digits(const vector<int>& x, const vector<int>& y) {
    if (x.size() != y.size()) {
        return x.size() < y.size() ? -1 : 1;
    }

    for (int i = (int)x.size() - 1; i >= 0; i--) {
        if (x[i] != y[i]) {
            return x[i] < y[i] ? -1 : 1;
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> c >> k;

    a.assign(c, vector<int>(k));

    for (int i = 0; i < c; i++) {
        for (int j = 0; j < k; j++) {
            cin >> a[i][j];
        }
    }

    /*
        Compute normalized base-8 volume for each color.

        volume[i] = sum_j a[i][j] * 8^j
    */
    vector<vector<int>> volume(c);

    for (int i = 0; i < c; i++) {
        volume[i] = normalize_base8(a[i]);
    }

    /*
        Sort color indices by decreasing total volume.
    */
    vector<int> order(c);
    iota(order.begin(), order.end(), 0);

    sort(order.begin(), order.end(), [&](int x, int y) {
        return compare_digits(volume[x], volume[y]) > 0;
    });

    /*
        sum_caps[j] = total available pieces of size 2^j
        among currently chosen colors.
    */
    vector<long long> sum_caps(k, 0);

    /*
        used_by_size[j] = how many pieces of size 2^j we will actually use.
    */
    vector<long long> used_by_size(k, 0);

    /*
        Chosen colors.
    */
    vector<int> chosen;

    /*
        Greedy feasibility checker.

        It also fills used_by_size[] if feasible.

        We start with the need for 8 corners of size 2^(k - 1).
        If unavailable, each missing corner is replaced by 8 smaller corners.
    */
    auto can_build = [&]() -> bool {
        fill(used_by_size.begin(), used_by_size.end(), 0);

        long long need = 8;

        /*
            sum_caps[j] is at most c * 1000 <= 1e6.
            Therefore, once need becomes extremely large, it can never be met.
            We clamp to avoid 64-bit overflow.
        */
        const long long CLAMP = 4000000000LL;

        for (int j = k - 1; j >= 0; j--) {
            if (sum_caps[j] >= need) {
                // We can finish construction using this size.
                used_by_size[j] = need;
                return true;
            }

            // Use all available pieces of this size.
            used_by_size[j] = sum_caps[j];

            long long missing = need - sum_caps[j];

            // Replace each missing piece by 8 smaller pieces.
            if (missing > CLAMP / 8) {
                need = CLAMP;
            } else {
                need = missing * 8;
            }
        }

        return false;
    };

    bool feasible = false;

    /*
        Add colors from largest volume to smallest.
        The first prefix that works uses the minimum possible number of colors.
    */
    for (int idx = 0; idx < c; idx++) {
        int color = order[idx];

        chosen.push_back(color);

        for (int j = 0; j < k; j++) {
            sum_caps[j] += a[color][j];
        }

        if (can_build()) {
            feasible = true;
            break;
        }
    }

    if (!feasible) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    /*
        Distribute the required pieces among chosen colors.

        result stores triples:
            color, size_index, count
    */
    vector<tuple<int, int, int>> result;

    for (int j = 0; j < k; j++) {
        long long need = used_by_size[j];

        for (int color : chosen) {
            if (need == 0) {
                break;
            }

            long long take = min<long long>(a[color][j], need);

            if (take > 0) {
                // Output colors are 1-indexed.
                result.emplace_back(color + 1, j, (int)take);
                need -= take;
            }
        }
    }

    cout << result.size() << '\n';

    for (auto [color, size_index, count] : result) {
        cout << color << ' ' << size_index << ' ' << count << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))

    if not data:
        return

    ptr = 0

    # Number of colors
    c = data[ptr]
    ptr += 1

    # We need to build one corner of size 2^k
    k = data[ptr]
    ptr += 1

    # a[i][j] = number of pieces of color i and size 2^j
    a = []

    for _ in range(c):
        row = data[ptr:ptr + k]
        ptr += k
        a.append(row)

    /*
    Python note:
    Python supports arbitrary precision integers, so we can store
    values like 8^1000 directly.

    Since 8^j = 2^(3j), multiplying by 8^j is the same as shifting
    left by 3*j bits.
    */
```

Python does not support block comments with `/* ... */`, so here is the correct full Python implementation:

```python
import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))

    if not data:
        return

    ptr = 0

    # Number of colors
    c = data[ptr]
    ptr += 1

    # We need to build one corner of size 2^k
    k = data[ptr]
    ptr += 1

    # a[i][j] = number of corners of color i and size 2^j
    a = []

    for _ in range(c):
        row = data[ptr:ptr + k]
        ptr += k
        a.append(row)

    # Compute total normalized volume of every color.
    #
    # A piece of size 2^j has normalized volume 8^j.
    # Since 8^j = 2^(3j), we can use bit shifting:
    #
    #     cnt * 8^j == cnt << (3 * j)
    #
    # Python integers have arbitrary precision, so this is safe.
    volumes = []

    for i in range(c):
        total = 0

        for j in range(k):
            total += a[i][j] << (3 * j)

        volumes.append(total)

    # Sort colors by decreasing total volume.
    order = sorted(range(c), key=lambda i: volumes[i], reverse=True)

    # sum_caps[j] = total number of chosen pieces of size 2^j
    sum_caps = [0] * k

    # used_by_size[j] = number of pieces of size 2^j that we will actually use
    used_by_size = [0] * k

    # Chosen colors
    chosen = []

    def can_build():
        """
        Check whether the currently chosen colors can build the big corner.

        Also fills used_by_size[].

        To build one corner of size 2^k, initially we need:
            8 corners of size 2^(k - 1)

        If we do not have enough pieces of some size j, each missing piece
        is replaced by 8 pieces of size j - 1.
        """

        nonlocal used_by_size

        used_by_size = [0] * k

        # Initial demand: 8 pieces of size 2^(k - 1)
        need = 8

        # Process from largest available size down to size 0
        for j in range(k - 1, -1, -1):
            if sum_caps[j] >= need:
                # We can finish using exactly 'need' pieces of this size.
                used_by_size[j] = need
                return True

            # Otherwise use all pieces of this size.
            used_by_size[j] = sum_caps[j]

            missing = need - sum_caps[j]

            # Replace every missing piece by 8 smaller pieces.
            need = missing * 8

        # If after size 0 we still have unmet demand, impossible.
        return False

    feasible = False

    # Add colors from largest volume to smallest.
    # The first feasible prefix gives the minimum possible number of colors.
    for color in order:
        chosen.append(color)

        for j in range(k):
            sum_caps[j] += a[color][j]

        if can_build():
            feasible = True
            break

    if not feasible:
        sys.stdout.write("NO SOLUTION\n")
        return

    # Distribute required pieces among chosen colors.
    #
    # Each result item is:
    #     color, size_index, count
    result = []

    for j in range(k):
        need = used_by_size[j]

        for color in chosen:
            if need == 0:
                break

            take = min(a[color][j], need)

            if take > 0:
                # Output colors are 1-indexed.
                result.append((color + 1, j, take))
                need -= take

    output = []

    output.append(str(len(result)))

    for color, size_index, count in result:
        output.append(f"{color} {size_index} {count}")

    sys.stdout.write("\n".join(output) + "\n")


if __name__ == "__main__":
    solve()
```