{"problem":{"name":"Rational Number System","description":{"content":"Let $r > 1$ be a rational number, and $p$ and $q$ be the numerator and denominator of $r$, respectively. That is, $p$ and $q$ are positive integers such that $r = \\frac{p}{q}$ and $\\gcd(p,q) = 1$. Let","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc149_f"},"statements":[{"statement_type":"Markdown","content":"Let $r > 1$ be a rational number, and $p$ and $q$ be the numerator and denominator of $r$, respectively. That is, $p$ and $q$ are positive integers such that $r = \\frac{p}{q}$ and $\\gcd(p,q) = 1$.\nLet the **base-$\\boldsymbol{r}$ expansion** of a positive integer $n$ be the integer sequence $(a_1, \\ldots, a_k)$ that satisfies all of the following conditions.\n\n*   $a_i$ is an integer between $0$ and $p-1$.\n*   $a_1\\neq 0$.\n*   $n = \\sum_{i=1}^k a_ir^{k-i}$.\n\nIt can be proved that any positive integer $n$ has a unique base-$r$ expansion.\n\n* * *\n\nYou are given positive integers $p$, $q$, $N$, $L$, and $R$. Here, $p$ and $q$ satisfy $1.01 \\leq \\frac{p}{q}$.\nConsider sorting all positive integers not greater than $N$ in ascending lexicographical order of their base-$\\frac{p}{q}$ expansions. Find the $L$\\-th, $(L+1)$\\-th, $\\ldots$, $R$\\-th positive integers in this list.\nAs usual, decimal notations are used in the input and output of positive integers.\nWhat is lexicographical order on sequences?A sequence $A = (A_1, \\ldots, A_{|A|})$ is said to be **lexicographically smaller** than $B = (B_1, \\ldots, B_{|B|})$ when 1. or 2. below is satisfied. Here, $|A|$ and $|B|$ denote the lengths of $A$ and $B$, respectively.\n\n1.  $|A|<|B|$ and $(A_{1},\\ldots,A_{|A|}) = (B_1,\\ldots,B_{|A|})$.\n2.  There is an integer $1\\leq i\\leq \\min{|A|,|B|}$ that satisfies both of the following.\n    *   $(A_{1},\\ldots,A_{i-1}) = (B_1,\\ldots,B_{i-1})$.\n    *   $A_i < B_i$.\n\n## Constraints\n\n*   $1\\leq p, q \\leq 10^9$\n*   $\\gcd(p,q) = 1$\n*   $1.01 \\leq \\frac{p}{q}$\n*   $1\\leq N\\leq 10^{18}$\n*   $1\\leq L\\leq R\\leq N$\n*   $R - L + 1\\leq 3\\times 10^5$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$p$ $q$ $N$ $L$ $R$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc149_f","tags":[],"sample_group":[["3 1 9 1 9","1\n3\n9\n4\n5\n2\n6\n7\n8\n\nThe base-$3$ expansions of the positive integers not greater than $9$ are as follows.\n\n1: (1),        2: (2),        3: (1, 0),\n4: (1, 1),     5: (1, 2),     6: (2, 0),\n7: (2, 1),     8: (2, 2),     9: (1, 0, 0)."],["3 2 9 1 9","1\n2\n3\n4\n6\n9\n7\n8\n5\n\nThe base-$\\frac32$ expansions of the positive integers not greater than $9$ are as follows.\n\n1: (1),        2: (2),        3: (2, 0),     \n4: (2, 1),     5: (2, 2),     6: (2, 1, 0),  \n7: (2, 1, 1),  8: (2, 1, 2),  9: (2, 1, 0, 0).\n\nOne can see that the base-$\\frac32$ expansion of $6$ is $(2,1,0)$, for instance, from $2\\cdot \\bigl(\\frac32\\bigr)^2 + 1\\cdot \\frac32 + 0\\cdot 1 = 6$."],["3 2 9 3 8","3\n4\n6\n9\n7\n8\n\nThis is the $3$\\-rd through $8$\\-th lines of the output to Sample Input 2."],["10 9 1000000000000000000 123456789123456789 123456789123456799","806324968563249278\n806324968563249279\n725692471706924344\n725692471706924345\n725692471706924346\n725692471706924347\n725692471706924348\n725692471706924349\n653123224536231907\n653123224536231908\n653123224536231909"]],"created_at":"2026-03-03 11:01:14"}}