#include using namespace std; struct Node { vector> out; // (to, weight) }; static int bitlen(int x) { return 32 - __builtin_clz((unsigned)x); } static vector toBits(int x, int k) { vector b(k); for (int i = 0; i < k; i++) b[i] = (x >> (k - 1 - i)) & 1; return b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L, R; cin >> L >> R; int maxLen = bitlen(R); vector nodes(1); // 1-indexed auto newNode = [&]() -> int { nodes.push_back(Node{}); return (int)nodes.size() - 1; }; int start = newNode(); int end = newNode(); vector Gen(maxLen, -1); // Gen[t] generates exactly t bits then reaches end Gen[0] = end; for (int t = 1; t < maxLen; t++) { int id = newNode(); Gen[t] = id; nodes[id].out.push_back({Gen[t-1], 0}); nodes[id].out.push_back({Gen[t-1], 1}); } auto addEdge = [&](int u, int v, int w) { nodes[u].out.push_back({v, w}); }; auto buildGE = [&](int k, const vector& aBits) -> int { vector memo(k + 1, -1); function dfs = [&](int pos) -> int { int rem = k - pos; if (rem == 0) return end; int &res = memo[pos]; if (res != -1) return res; int id = newNode(); res = id; int lb = aBits[pos]; if (lb == 0) { addEdge(id, dfs(pos + 1), 0); addEdge(id, Gen[rem - 1], 1); } else { addEdge(id, dfs(pos + 1), 1); } return id; }; return dfs(1); }; auto buildLE = [&](int k, const vector& bBits) -> int { vector memo(k + 1, -1); function dfs = [&](int pos) -> int { int rem = k - pos; if (rem == 0) return end; int &res = memo[pos]; if (res != -1) return res; int id = newNode(); res = id; int hb = bBits[pos]; if (hb == 0) { addEdge(id, dfs(pos + 1), 0); } else { addEdge(id, Gen[rem - 1], 0); addEdge(id, dfs(pos + 1), 1); } return id; }; return dfs(1); }; auto buildBetween = [&](int k, const vector& aBits, const vector& bBits) -> int { static int memo[25][2][2]; for (int i = 0; i <= k; i++) for (int tl = 0; tl < 2; tl++) for (int th = 0; th < 2; th++) memo[i][tl][th] = -1; function dfs = [&](int pos, int tL, int tH) -> int { int rem = k - pos; if (rem == 0) return end; if (!tL && !tH) return Gen[rem]; int &res = memo[pos][tL][tH]; if (res != -1) return res; int id = newNode(); res = id; int lo = tL ? aBits[pos] : 0; int hi = tH ? bBits[pos] : 1; for (int x = lo; x <= hi; x++) { int ntL = tL && (x == aBits[pos]); int ntH = tH && (x == bBits[pos]); int to = dfs(pos + 1, ntL, ntH); addEdge(id, to, x); } return id; }; return dfs(1, 1, 1); }; int lenL = bitlen(L), lenR = bitlen(R); for (int k = lenL; k <= lenR; k++) { long long minK = 1LL << (k - 1); long long maxK = (1LL << k) - 1; long long low = max(L, minK); long long high = min(R, maxK); if (low > high) continue; int entry = -1; if (low == minK && high == maxK) { entry = Gen[k - 1]; } else if (high == maxK) { auto aBits = toBits((int)low, k); entry = buildGE(k, aBits); } else if (low == minK) { auto bBits = toBits((int)high, k); entry = buildLE(k, bBits); } else { auto aBits = toBits((int)low, k); auto bBits = toBits((int)high, k); entry = buildBetween(k, aBits, bBits); } addEdge(start, entry, 1); } int n = (int)nodes.size() - 1; if (n > 100) { // Should not happen with this construction for given constraints. // If it does, fall back to a trivial (but invalid by constraints) output to avoid UB. // However, expected never to trigger. return 0; } cout << n << "\n"; for (int i = 1; i <= n; i++) { cout << nodes[i].out.size(); for (auto [to, w] : nodes[i].out) { cout << ' ' << to << ' ' << w; } cout << "\n"; } return 0; }