#include using namespace std; 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(); // 0 int START = addNode(); // 1 // Free chain vector freeChain(21, -1); freeChain[0] = END_NODE; for (int k = 1; k <= 20; k++) { int u = addNode(); adj[u].push_back({freeChain[k-1], 0}); adj[u].push_back({freeChain[k-1], 1}); freeChain[k] = u; } // Decompose range [lo, hi] at bit length k into aligned blocks // Each aligned block is a prefix + free chain // Return list of (prefix_bits, free_length) pairs // A prefix of length p followed by free_length = k-p means the block starts at prefix * 2^(k-p) // and has 2^(k-p) elements // Standard canonical decomposition of [lo, hi] into aligned blocks // Returns list of (start, power) pairs where each block is [start, start + 2^power - 1] auto decompose = [](int lo, int hi, int k) -> vector> { vector> blocks; int x = lo; while (x <= hi) { // Find largest power p such that: // 1. x is a multiple of 2^p // 2. x + 2^p - 1 <= hi int p = 0; while (p < k && (x % (1 << (p+1)) == 0) && (x + (1 << (p+1)) - 1 <= hi)) { p++; } blocks.push_back({x, p}); x += (1 << p); } return blocks; }; int lenL = 32 - __builtin_clz(L); int lenR = 32 - __builtin_clz(R); 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; int loSuf = cL - rs; int hiSuf = cR - rs; if (suffLen == 0) { adj[START].push_back({END_NODE, 1}); continue; } // Decompose [loSuf, hiSuf] into aligned blocks auto blocks = decompose(loSuf, hiSuf, suffLen); // For each block (start, power): the block is [start, start + 2^power - 1] // prefix = start >> power (the upper bits of start) // prefix has (suffLen - power) bits // The path: START -1-> prefix bits -> freeChain[power] -> ... -> END // Build a trie of the prefixes, with leaves connecting to freeChain // The trie is a DAG where shared prefixes share nodes // Build prefix paths // For each block, we have a prefix (suffLen - power bits) followed by free[power] struct TrieNode { int nodeId; int children[2]; // -1 if not set TrieNode() : nodeId(-1) { children[0] = children[1] = -1; } }; vector trie(1); // root for (auto& [start, power] : blocks) { int prefLen = suffLen - power; int prefix = (prefLen > 0) ? (start >> power) : 0; int cur = 0; // trie root for (int i = prefLen - 1; i >= 0; i--) { int bit = (prefix >> i) & 1; if (trie[cur].children[bit] == -1) { trie[cur].children[bit] = trie.size(); trie.emplace_back(); } cur = trie[cur].children[bit]; } // At leaf: connect to freeChain[power] trie[cur].nodeId = freeChain[power]; } // Assign DAG node IDs to trie nodes (except leaves that directly use freeChain) // Process trie BFS and create nodes // Root trie node connects to START with weight 1 function buildTrie = [&](int t) -> int { if (trie[t].nodeId != -1) return trie[t].nodeId; if (trie[t].children[0] == -1 && trie[t].children[1] == -1) return -1; int u = addNode(); trie[t].nodeId = u; for (int b = 0; b < 2; b++) { if (trie[t].children[b] != -1) { int child = buildTrie(trie[t].children[b]); if (child != -1) { adj[u].push_back({child, b}); } } } return u; }; int root = buildTrie(0); 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 (!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; }