Monkeys in the Emei Mountain

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define YES cout << "Yes" << endl
#define NO  cout << "No" << endl

using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 105;
const int VMAX = 5e4+5;
const int INF = 2e9+5;
const int SOURCE = 0;
const int SINK = NMAX + VMAX - 1;

struct Edge {
    int dest, flow, rev;
};

struct Monkey {
    int v, l, r;
};

int n, m;
vector<Edge> g[VMAX + NMAX];
int d[VMAX + NMAX], last[VMAX + NMAX];
Monkey a[NMAX];
vector<pii> ans[NMAX];

void io() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
}

void read() {
    cin >> n >> m;
    if (n == 0) exit(0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].v >> a[i].l >> a[i].r;
        a[i].l++;
    }
}

void add_edge(int x, int y, int c) {
    g[x].push_back({ y, c, sz(g[y]) });
    g[y].push_back({ x, 0, sz(g[x]) - 1 });
}

bool bfs() {
    memset(d, 0, sizeof(d));
    memset(last, 0, sizeof(last));

    queue<int> q;
    q.push(SOURCE);
    d[SOURCE] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == SINK) continue;
        for (auto &it : g[u]) {
            if (!d[it.dest] && it.flow > 0) {
                d[it.dest] = d[u] + 1;
                q.push(it.dest);
            }
        }
    }

    return d[SINK];
}

int dfs(int x = SOURCE, int flow = INF) {
    if (x == SINK)
        return flow;

    for (; last[x] < sz(g[x]); last[x]++) {
        Edge &e = g[x][last[x]];
        if (e.flow > 0 && d[e.dest] == d[x] + 1) {
            if (int ret = dfs(e.dest, min(flow, e.flow))) {
                e.flow -= ret;
                g[e.dest][e.rev].flow += ret;
                return ret;
            }
        }
    }

    return 0;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) {
        while (int flow = dfs())
            max_flow += flow;
    }
    return max_flow;
}

void solve(int t) {
    int s = 0;
    for (int i = 0; i < NMAX + VMAX; i++)
        g[i].clear();
    for (int i = 1; i < VMAX; i++)
        add_edge(n + i, SINK, m);
    for (int i = 1; i <= n; i++) {
        add_edge(SOURCE, i, a[i].v);
        s += a[i].v;
        for (int j = a[i].l; j <= a[i].r; j++)
            add_edge(i, n + j, 1);
    }
    int max_flow = dinic();
    cout << "Case " << t << ": ";
    if (max_flow != s) NO;
    else {
        YES;
        for (int i = 1; i <= n; i++) {
            for (auto &it : g[i]) {
                if (it.dest == SOURCE || it.flow) continue;
                if (ans[i].empty() || ans[i].back().se != it.dest - n - 1)
                    ans[i].push_back({it.dest - n, it.dest - n});
                else
                    ans[i].back().se++;
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << sz(ans[i]);
            for (auto &it : ans[i])
                cout << " (" << it.fi - 1 << ',' << it.se << ')';
            ans[i].clear();
            cout << endl;
        }
    }
}

signed main() {
    io();
    for (int t = 1; ; t++) {
        read();
        solve(t);
    }
    return 0;
}