#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L, R; cin >> L >> R; // Find bit lengths int lenL = (L == 0) ? 1 : 32 - __builtin_clz(L); int lenR = (R == 0) ? 1 : 32 - __builtin_clz(R); struct Edge { int to, w; }; vector> adj; int n = 0; auto addNode = [&]() { adj.emplace_back(); return n++; }; int END = addNode(); // 0 int START = addNode(); // 1 // Free chain map freeNode; freeNode[0] = END; 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; }; // For each bit length, build the sub-DAG // State: (position, tight_lo, tight_hi) // position: current bit position (0 = MSB after the leading 1) // tight_lo: still matching L's bits // tight_hi: still matching R's bits for (int len = lenL; len <= lenR; len++) { int rs = 1 << (len-1); int re = (1 << len) - 1; int cL = max(L, rs); int cR = min(R, re); if (cL > cR) continue; int suffLen = len - 1; // bits after MSB int loSuf = cL - rs; int hiSuf = cR - rs; // Extract bits vector loBits(suffLen), hiBits(suffLen); for (int i = 0; i < suffLen; i++) { loBits[i] = (loSuf >> (suffLen - 1 - i)) & 1; hiBits[i] = (hiSuf >> (suffLen - 1 - i)) & 1; } // Build DP // States: (pos, tight_lo, tight_hi) // For memoization, use a map // Node IDs for each state map, int> stateNode; function build = [&](int pos, bool tlo, bool thi) -> int { if (pos == suffLen) return END; auto key = make_tuple(pos, tlo, thi); auto it = stateNode.find(key); if (it != stateNode.end()) return it->second; if (!tlo && !thi) { // Free state return stateNode[key] = getFree(suffLen - pos); } int lo_bit = tlo ? loBits[pos] : 0; int hi_bit = thi ? hiBits[pos] : 1; // Enumerate valid bits struct ChildInfo { int bit; int nextNode; }; vector children; for (int b = lo_bit; b <= hi_bit; b++) { bool next_tlo = tlo && (b == loBits[pos]); bool next_thi = thi && (b == hiBits[pos]); int child = build(pos + 1, next_tlo, next_thi); children.push_back({b, child}); } if (children.empty()) return stateNode[key] = -1; // Check if this is equivalent to a free node if (children.size() == 2 && children[0].nextNode == children[1].nextNode && children[0].nextNode == getFree(suffLen - pos - 1)) { return stateNode[key] = getFree(suffLen - pos); } int u = addNode(); for (auto& c : children) { adj[u].push_back({c.nextNode, c.bit}); } return stateNode[key] = u; }; int root = build(0, loSuf != 0 || true, hiSuf != ((1 << suffLen) - 1) || true); // Actually, always start tight root = build(0, true, true); if (root >= 0) { adj[START].push_back({root, 1}); } } // 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); } } } // Renumber 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]; vector> edges; for (auto& e : adj[u]) { if (newId.count(e.to)) { edges.push_back({newId[e.to], e.w}); } } cout << edges.size(); for (auto& [to, w] : edges) cout << " " << to << " " << w; cout << "\n"; } return 0; }