#include using namespace std; // Try: build the DAG using interval decomposition, but with additional // optimization: use multi-edges (multiple edges with same weight from same node) // to split ranges and reuse more free chain nodes. int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L, R; cin >> L >> R; struct Edge { int to, w; }; vector> adj; int n = 0; auto addNode = [&]() { adj.emplace_back(); return n++; }; int END_NODE = addNode(); int START = addNode(); // Free chain map freeNode; freeNode[0] = END_NODE; function getFree = [&](int k) -> int { if (freeNode.count(k)) return freeNode[k]; int ch = getFree(k-1); int u = addNode(); adj[u].push_back({ch, 0}); adj[u].push_back({ch, 1}); return freeNode[k] = u; }; // Build range with potential multi-edge optimization map, int> memo; function buildRange = [&](int k, int lo, int hi) -> int { if (lo > hi || k < 0) return -1; if (k == 0) return (lo == 0 && hi == 0) ? END_NODE : -1; if (lo == 0 && hi == (1 << k) - 1) return getFree(k); auto key = make_tuple(k, lo, hi); if (memo.count(key)) return memo[key]; int mid = 1 << (k-1); // Standard split int left = -1, right = -1; if (lo <= min(hi, mid-1)) left = buildRange(k-1, lo, min(hi, mid-1)); if (max(lo, mid) <= hi) right = buildRange(k-1, max(lo, mid) - mid, hi - mid); if (left == -1 && right == -1) return memo[key] = -1; // Check if this node would be a single-edge (forced bit) node // If so, check if we can merge with the parent int u = addNode(); if (left != -1) adj[u].push_back({left, 0}); if (right != -1) adj[u].push_back({right, 1}); return memo[key] = u; }; int lenL = 32 - __builtin_clz(L); int lenR = 32 - __builtin_clz(R); for (int len = lenL; len <= lenR; len++) { int rs = 1 << (len-1), re = (1 << len) - 1; int cL = max(L, rs), cR = min(R, re); if (cL > cR) continue; int suffLen = len - 1; if (suffLen == 0) { adj[START].push_back({END_NODE, 1}); continue; } int target = buildRange(suffLen, cL - rs, cR - rs); if (target >= 0) adj[START].push_back({target, 1}); } // Now try to optimize: for each single-edge node, check if its parent // can absorb it by adding multi-edges. // This is a post-processing step. // Find single-edge nodes (not START, not END) // A single-edge node has exactly one outgoing edge. // Its parent has an edge to it. We want to replace: // parent -> (w) -> single_node -> (w2) -> child // with: // parent -> (w) -> new_node -> (w2) -> child // where new_node IS something else we can reuse. // But new_node would need the same remaining depth as single_node. // Since single_node's depth is unique, we can't reuse. // Alternative: absorb into parent using multi-edges. // parent -> (w) -> single_node -> (w2) -> child // Replace with: parent -> (w) -> child directly? NO - loses a bit. // We can't optimize single-edge nodes away. // Remove unreachable vector reach(n, false); queue q; q.push(START); reach[START] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (auto& e : adj[u]) if (e.to >= 0 && !reach[e.to]) { reach[e.to] = true; q.push(e.to); } } map newId; int cnt = 0; newId[START] = ++cnt; for (int i = 0; i < n; i++) if (i != START && reach[i]) newId[i] = ++cnt; cout << cnt << "\n"; vector inv(cnt + 1); for (auto& [old, nw] : newId) inv[nw] = old; for (int i = 1; i <= cnt; i++) { int u = inv[i]; cout << adj[u].size(); for (auto& e : adj[u]) cout << " " << newId[e.to] << " " << e.w; cout << "\n"; } return 0; }