(Analysis by Agastya Goel)

First, let's examine the number of times a cow can move from the front of the line to the middle of the line. In particular, if a cow is at the front of the line right before time $t$, it will be at position $\lfloor \frac{t}{2}\rfloor$ before time $t+1$, and then at position $0$ again before time $t + 1 + \lfloor \frac{t}{2}\rfloor$, which is $\geq 3/2 \cdot t$. In particular, if a cow is at the front of the line at time $t$, then for them to reach the front of the line $k$ more times would require at least until time $(3/2)^k t$. Thus, within the first $T$ timesteps, any individual cow can only reach the front of the line $O(\log T)$ times. Now, we can examine how to simulate each of the two cases.

Type 1 queries: We can efficiently simulate a cow's movement by using the following three rules until we reach the desired timestep.

  1. Cow $i$ will not begin to move until timestep $2i$.
  2. If cow $i$ is at position $p$ before time $t \geq 2i$, it will be at position $0$ before time $t + p$.
  3. If cow $i$ is at position $0$ before time $t$, it will be at position $\lfloor \frac{t}{2}\rfloor$ before time $t+1$.

Since a cow can only move from the front of the line to the middle of the line $O(\log t)$ times, we only have to simulate $O(\log t)$ steps.

Type 2 queries: Let $c(p, t)$ be the cow at position $p$ after time $t$. If we treat all cows as starting in an infinitely long line, cow $c$ always starts at position $c$. Thus, $c(p, 0) = p$. We start with the following rules derived from how the line evolves:

  1. $c(\lfloor \frac{t}{2}\rfloor, t) = c(0, t-1)$
  2. $c(p, t) = p$ for $p > \lfloor \frac{t}{2}\rfloor$.
  3. $c(p, t) = c(p+1, t-1)$ for $p < \lfloor \frac{t}{2}\rfloor$.

To optimize step 3, we need to move more than one step at a time. That is, we need to find a near-maximum $\Delta$ such that $c(p, t) = c(p+\Delta, t-\Delta)$. To do this, we need the condition $p < \lfloor \frac{t}{2}\rfloor$ to hold for the last step, which means that $p + \Delta - 1 < \lfloor \frac{t - \Delta + 1}{2}\rfloor$. We can then safely pick

$$\Delta = \left\lfloor\frac{t-2p}{3}\right\rfloor.$$
This estimate of $\Delta$ is conservative. That is, after performing $\Delta$ steps, we might still be in the case where $p < \lfloor \frac{t}{2}\rfloor$. In that case, we can perform a constant number of steps of size $1$. Either way, we only ever perform a constant number of steps of type 3 before performing a step of type 1, so we only take $O(\log t)$ steps total to compute $c(p, t)$.

Thus, both cases take $O(\log t)$ per query, for a final complexity of $O(Q \log t)$.

Python full solution: 

def get_pos(i, t):
    if t < 2 * i:
        return i
    cur_t = 2 * i - 1
    t -= cur_t
    pos = i
    while t >= 0:
        if t <= pos:
            return pos - t
        else:
            # otherwise, simulate one loop around
            cur_t += pos
            t -= pos
            pos = 0
            
            cur_t += 1
            t -= 1
            pos = cur_t // 2
    assert t >= 0 # we should never overshoot
    return pos

def at_pos(p, t):
    if t == 0:
        return p
    if p < t//2:
        step = max(1, (t - 2 * p) // 3)
        return at_pos(p + step, t - step)

    if p == t//2:
        return at_pos(0, t - 1)

    return p

q = int(input())

for i in range(q):
    a, b, c = map(int, input().split())
    if a == 1:
        print(get_pos(b, c))
    else:
        print(at_pos(b, c))