Lineup Queries

There is a line of cows, initially (i.e. at time $t=0$) containing only cow $0$ at position $0$ (here, a cow is at position $k$ if there are $k$ cows in front of it). At time $t$ for $t=1,2,3,\dots$, the cow at position 0 moves to position $\lfloor t/2\rfloor$, every cow in positions $1\dots \lfloor t/2\rfloor$ moves forward one position, and cow $t$ joins the line at the end of the line (position $t$).

Answer $Q$ ($1\le Q\le 10^5$) independent queries, each of one of the following types:

1. At what position is cow $c$ immediately after time $t$ ($0\le c\le t\le 10^{18}$)?
2. Which cow is at position $x$ immediately after time $t$ ($0\le x\le t\le 10^{18}$)?

Lineups immediately after various times:

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

Immediately after $t=9$, the location of cow $4$ is $2$, and the cow located at position $2$ is $4$.

Problem credits: Agastya Goel

Source: USA Computing Olympiad.

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Submit