Problem F
Fizz Buzz
Everybody loves easy problems. And no problem is easier than the Fizz Buzz problem. Indeed, F in Finals stands for Fizz Buzz!
Let $F_0$ denote the following string:
F_in_Finals_stands_for_Fizz_Buzz!
We can recursively generate $F_ i$ (for $i \geq 1$) with the following rule:
-
$F_ i$ is the string obtained by replacing all characters F in $F_{i-1}$ by $F_0$ simultaneously.
For example, $F_1$ is the following string (without the line breaks):
F_in_Finals_stands_for_Fizz_Buzz!_in_ F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_ F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!
And $F_2$ is the following string (without the line breaks):
F_in_Finals_stands_for_Fizz_Buzz!_in_ F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_ F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!_in_ F_in_Finals_stands_for_Fizz_Buzz!_in_ F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_ F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!inals_stands_for_ F_in_Finals_stands_for_Fizz_Buzz!_in_ F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_ F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!izz_Buzz!
You can keep generating $F_ i$ for all non-negative integers $i$. To test whether you understand this operation, you should answer $Q$ questions $(X_ j, Y_ j)$: what is the $X_ j$-th character of $F_{Y_ j}$?
Input
The first line of input contains one integer $Q$, the number of questions you need to answer ($1 \leq Q \leq 300\, 000$).
The next $Q$ lines of input each contain two integers $X_ j$ and $Y_ j$ ($1 \leq X_ j \leq 10^{18}$; $0 \leq Y_ j \leq 10^{18}$).
Output
Output a string of length $Q$. The $j$-th character of the string should be the $X_ j$-th character of $F_{Y_ j}$. If there are less than $X_ j$ characters in $F_{Y_ j}$, output the character ? instead.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 157 2 71 1 26 2 128 1 417 2 29 0 250 2 63 1 32 0 34 0 |
Fizz!Buzz? |
