{"raw_statement":[{"iden":"problem statement","content":"For a sequence of integers $P = (P_1, \\ldots, P_M)$, let $f(P)$ denote the sequence obtained by inserting $P_i + P_{i+1}$ between $P_i$ and $P_{i+1}$ for each $1\\leq i\\leq M-1$. More formally:\n\n*   Let $Q_i = P_i + P_{i+1}$ for each $1\\leq i\\leq M - 1$.\n*   Let $f(P)$ be defined as a sequence of $2M-1$ integers $f(P) = (P_1, Q_1, P_2, Q_2, \\ldots, P_{M-1}, Q_{M-1}, P_M)$.\n\n* * *\n\nGiven are three positive integers $a$, $b$, and $N$ where $a, b\\leq N$. Let us begin with a sequence $A = (a, b)$ and define a sequence $B = (B_1, B_2, \\ldots)$ as follows.\n\n*   Do the following $N$ times: replace $A$ with $f(A)$.\n*   Then, remove from $A$ all values greater than $N$ and let $B$ be the resulting sequence.\n\nFind $B_L, \\ldots, B_R$."},{"iden":"constraints","content":"*   $1\\leq N\\leq 3\\times 10^5$\n*   $1\\leq a, b\\leq N$\n*   $1\\leq L\\leq R\\leq 10^{18}$\n*   $R - L < 3\\times 10^5$\n*   $R$ is at most the number of elements in the sequence $B$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$a$ $b$ $N$ \n$L$ $R$"},{"iden":"sample input 1","content":"1 1 4\n1 7"},{"iden":"sample output 1","content":"1 4 3 2 3 4 1\n\nInitially, $A = (1, 1)$. The replacements of $A$ with $f(A)$ take place as follows.\n\n*   After the first replacement: $A = (1, 2, 1)$.\n*   After the second replacement: $A = (1, 3, 2, 3, 1)$.\n*   After the third replacement: $A = (1, 4, 3, 5, 2, 5, 3, 4, 1)$.\n*   After the fourth replacement: $A = (1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1)$.\n\nThus, we have $B = (1, 4, 3, 2, 3, 4, 1)$. We should report the $1$\\-st through $7$\\-th elements of this sequence."},{"iden":"sample input 2","content":"1 1 4\n2 5"},{"iden":"sample output 2","content":"4 3 2 3\n\nAgain, we have $B = (1, 4, 3, 2, 3, 4, 1)$. We should report the $2$\\-nd through $5$\\-th elements of this sequence."},{"iden":"sample input 3","content":"2 1 10\n5 15"},{"iden":"sample output 3","content":"8 3 10 7 4 9 5 6 7 8 9"},{"iden":"sample input 4","content":"10 10 10\n2 2"},{"iden":"sample output 4","content":"10"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}