{"problem":{"name":"Divide Interval","description":{"content":"For non-negative integers $l$ and $r$ $(l < r)$, let $S(l, r)$ denote the sequence $(l, l+1, \\ldots, r-2, r-1)$ formed by arranging integers from $l$ through $r-1$ in order. Furthermore, a sequence is","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc349_d"},"statements":[{"statement_type":"Markdown","content":"For non-negative integers $l$ and $r$ $(l < r)$, let $S(l, r)$ denote the sequence $(l, l+1, \\ldots, r-2, r-1)$ formed by arranging integers from $l$ through $r-1$ in order. Furthermore, a sequence is called a good sequence if and only if it can be represented as $S(2^i j, 2^i (j+1))$ using non-negative integers $i$ and $j$.\nYou are given non-negative integers $L$ and $R$ $(L < R)$. Divide the sequence $S(L, R)$ into the fewest number of good sequences, and print that number of sequences and the division. More formally, find the minimum positive integer $M$ for which there is a sequence of pairs of non-negative integers $(l_1, r_1), (l_2, r_2), \\ldots, (l_M, r_M)$ that satisfies the following, and print such $(l_1, r_1), (l_2, r_2), \\ldots, (l_M, r_M)$.\n\n*   $L = l_1 < r_1 = l_2 < r_2 = \\cdots = l_M < r_M = R$\n*   $S(l_1, r_1), S(l_2, r_2), \\ldots, S(l_M, r_M)$ are good sequences.\n\nIt can be shown that there is only one division that minimizes $M$.\n\n## Constraints\n\n*   $0 \\leq L < R \\leq 2^{60}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$L$ $R$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc349_d","tags":[],"sample_group":[["3 19","5\n3 4\n4 8\n8 16\n16 18\n18 19\n\n$S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)$ can be divided into the following five good sequences, which is the minimum possible number:\n\n*   $S(3,4)=S(2^0\\cdot 3,2^0\\cdot4)=(3)$\n*   $S(4,8)=S(2^2\\cdot 1,2^2\\cdot 2)=(4,5,6,7)$\n*   $S(8,16)=S(2^3\\cdot 1,2^3\\cdot 2)=(8,9,10,11,12,13,14,15)$\n*   $S(16,18)=S(2^1\\cdot 8,2^1\\cdot 9)=(16,17)$\n*   $S(18,19)=S(2^0\\cdot 18,2^0\\cdot 19)=(18)$"],["0 1024","1\n0 1024"],["3940649673945088 11549545024454656","8\n3940649673945088 3940649673949184\n3940649673949184 4503599627370496\n4503599627370496 9007199254740992\n9007199254740992 11258999068426240\n11258999068426240 11540474045136896\n11540474045136896 11549270138159104\n11549270138159104 11549545016066048\n11549545016066048 11549545024454656"]],"created_at":"2026-03-03 11:01:14"}}