P13996 【MX-X19-T5】「FeOI Round 4.5」Angel's Clover

[Angel's Clover - DIVELA / Kagamine Len / MORE MORE JUMP!](https://www.bilibili.com/video/BV1oh2PYcEiW) > 全身全霊！MORE MORE JUMP!!

Minori has a $01$ sequence $s$, initially $s = [0, 1]$. The indices of this sequence start from $0$. For a $01$ sequence $s = [s_0, \ldots, s_{\lvert s \rvert - 1}]$ with indices starting from $0$, define the new $01$ sequence $t = f(s)$ obtained after one $f$-transformation as: - Initially, $t$ is empty. - For each $i = 0, \ldots, \lvert s \rvert - 1$, append to the end of $t$: - $1$ copy of $i \bmod 2$ (if $s_i = 0$); - $3$ copies of $i \bmod 2$ (if $s_i = 1$). - The indices of $t$ also start from $0$. For example, $f([0, 1]) = [0, 1, 1, 1]$, and $f([0, 1, 1, 1]) = [0, 1, 1, 1, 0, 0, 0, 1, 1, 1]$. For a non-negative integer $x$, define the notation $f^x(s)$ as the sequence obtained by applying the $f$-transformation to $s$ consecutively $x$ times. Minori will give you $q$ queries. Each query provides two non-negative integers $x, r$, and asks for the value of the element at index $r$ in $f^x(s)$. If the length of $f^x(s)$ is $\le r$, meaning there is no element at index $r$, you must report that.

The first line contains a positive integer $q$. The next $q$ lines each contain two non-negative integers $x, r$.

For each query, output one line. If an element at index $r$ exists, output a non-negative integer representing its value; otherwise, output `-1`.

**【Sample Explanation】** The initial sequence is $[0,1]$. After one transformation, the sequence becomes $[0,1,1,1]$. After two transformations, the sequence becomes $[0,1,1,1,0,0,0,1,1,1]$. **【Data Range】** **The test cases are not equally weighted. See the score column for details.** | Test Case ID | $x \le$ | $q \le$ | Special Properties | Score | |:------------:|:-----------:|:---------:|:------------------:|:-----:| | $1$ | $3$ | $10^4$ | None | $12$ | | $2$ | $10$ | $20$ | None | $19$ | | $3$ | $10^{18}$ | $10$ | No answer is $0$ | $19$ | | $4$ | $10^{18}$ | $20$ | $x\ge 10^{12}$ | $10$ | | $5$ | $10^{18}$ | $10^4$ | None | $40$ | For all test cases, $1\le q\le 10^4$, $0\le x,r\le 10^{18}$. *Translated by DeepSeek V3.1*