<|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 `a[i][j]`.

---

### 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 after carry propagation.

---

### 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 `need = 8`. Process sizes from largest to smallest:

For size `j`:

- If `sum_caps[j] >= need`, use exactly `need` pieces of size `j`, and construction is complete.
- Otherwise, use all `sum_caps[j]` pieces.
- The missing amount `missing = need - sum_caps[j]` must be replaced by `8` pieces each of size `j - 1`:

```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:

```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`, iterate over chosen colors and take as many available pieces of size `j` as possible until demand is zero.

Each output line is:

```text
color size_index count
```

Colors are output 1-indexed.

---

### Complexity

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

Fine for `c, k <= 1000`.

---

## 4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int c, k;
vector<vector<int>> a;

void read() {
    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];
        }
    }
}

vector<int> normalize_base8(const vector<int>& coeffs) {
    vector<int> digits;
    digits.reserve(coeffs.size() + 4);
    int64_t carry = 0;
    for(int v: coeffs) {
        int64_t cur = (int64_t)v + carry;
        digits.push_back((int)(cur % 8));
        carry = cur / 8;
    }

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

    while(!digits.empty() && digits.back() == 0) {
        digits.pop_back();
    }

    return digits;
}

int cmp_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;
}

void solve() {
    // A "corner" of size 2^j sits inside a bounding cube of side 2^{j+1} and
    // occupies 4 of the 8 unit sub-cubes meeting at one of its corners. The
    // opposite four sub-cubes form another corner, so two corners of size 2^j
    // tile a cube of side 2^{j+1}. Hence the big corner of size 2^k splits
    // into 4 cubes of side 2^k = 8 corners of size 2^{k-1}, and recursively
    // any corner of size 2^j can be replaced by 8 corners of size 2^{j-1}.
    //
    // Because of that recursion, the only constraint on which multiset of
    // small corners fills the big corner is the total volume: if x_j corners
    // of size 2^j are chosen with sum x_j * 8^j = 8^k, the tiling is always
    // realizable. The per-level cap x_j <= N_j (demand cascading from above)
    // is automatic, since sum_{i >= j} x_i * 8^i <= 8^k forces x_j to fit
    // the remaining demand. So feasibility for a chosen set S of colors is
    // just sum_{c in S, j} a[c][j] * 8^j >= 8^k.
    //
    // Minimizing the number of colors is then "smallest prefix of largest
    // volumes that reaches the target". Volumes are up to 8^1000, so each
    // color's volume is stored as a base-8 digit vector (after normalizing
    // a[c][.] by carry propagation), and colors are sorted by lexicographic
    // comparison of those digit vectors. We add colors one at a time in that
    // order and after each addition run the top-down greedy on the combined
    // per-size capacities T_j to test feasibility.
    //
    // The top-down greedy itself uses 64-bit arithmetic with a clamp on the
    // unmet demand N: as long as N stays below ~4e9 we propagate it
    // exactly; once it exceeds that bound it can no longer be absorbed by
    // any T_j (capped at c * 1000 = 1e6), so we clamp and treat the run as
    // infeasible. When feasibility holds, the loop terminates at the first
    // level where T_j >= N_j, giving the totals x_j; these are then split
    // across the chosen colors in any order, respecting a[c][j].

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

    vector<int> order(c);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int u, int v) {
        return cmp_digits(vol_digits[u], vol_digits[v]) > 0;
    });

    vector<int64_t> sum_caps(k, 0);
    vector<int64_t> x(k, 0);
    vector<int> chosen;
    bool feasible = false;

    auto try_greedy = [&]() -> bool {
        fill(x.begin(), x.end(), (int64_t)0);
        int64_t N = 8;
        const int64_t CLAMP = (int64_t)4e9;
        for(int j = k - 1; j >= 0; j--) {
            if(sum_caps[j] >= N) {
                x[j] = N;
                N = 0;
                break;
            }

            x[j] = sum_caps[j];
            int64_t rem = N - sum_caps[j];
            if(rem > CLAMP / 8) {
                N = CLAMP;
            } else {
                N = rem * 8;
            }
        }
        return N == 0;
    };

    for(int idx = 0; idx < c; idx++) {
        int cc = order[idx];
        chosen.push_back(cc);
        for(int j = 0; j < k; j++) {
            sum_caps[j] += a[cc][j];
        }

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

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

    vector<tuple<int, int, int>> result;
    for(int j = 0; j < k; j++) {
        int64_t need = x[j];
        for(int cc: chosen) {
            if(need == 0) {
                break;
            }

            int64_t take = min((int64_t)a[cc][j], need);
            if(take > 0) {
                result.push_back({cc + 1, j, (int)take});
                need -= take;
            }
        }
    }

    cout << result.size() << "\n";
    for(auto& [col, sz, cnt]: result) {
        cout << col << ' ' << sz << ' ' << cnt << "\n";
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. 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.
    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()
```
