P14977 [USACO26JAN1] Lineup Queries S

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}$)? 1. Which cow is at position $x$ immediately after time $t$ ($0\le x\le t\le 10^{18}$)?

The first line contains $Q$, the number of queries. The next $Q$ lines each contain three integers specifying a query either of the form "$1$ $c$ $t$" or "$2$ $x$ $t$".

Output the answer to each query on a separate line.

Lineups immediately after various times: ```none 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$. --- - Input 3: $Q\le 1000, t\le 100$ - Input 4: $t\le 5000$ - Inputs 5-8: All queries are of type 1. - Inputs 9-12: All queries are of type 2.