혹 떼러 갔다 혹 붙여 온다

"혹 떼러 갔다 혹 붙여 온다: 애드 혹"

혹부리 영감은 얼굴에 달린 커다란 혹을 떼고 싶어 도깨비를 찾아갔지만, 장난을 좋아하는 도깨비는 오히려 혹을 더 붙이려고 한다. 편의상 모든 혹은 선분으로 간주하며, 최초에 혹부리 영감에게는 길이가 무한히 긴 $0$번 혹 한 개가 달려 있다. 도깨비는 항상 모든 혹의 연결 관계가 트리 구조를 이루도록 혹을 붙인다. 즉, $0$번 혹을 제외한 모든 혹의 윗부분은 정확히 하나의 혹의 아래에 닿아 있다.

도깨비는 혹을 붙이면서 혹부리 영감에게 "이 혹에서 이만큼 위에는 무슨 혹이 있을까~요?"라는 문제를 낸다. 이 문제를 전부 맞히면 마지막엔 모든 혹을 떼어 주기로 약속하였다. 문제를 푸는 데 자신이 없는 혹부리 영감을 대신하여 여러분이 답을 알려 주자.

혹을 어떻게 붙일지 미리 예측하는 것을 막기 위해, 도깨비가 특이한 방법으로 혹을 붙일 위치를 정한다는 점에 주의하자.

첫째 줄에 도깨비의 행동 횟수 $Q$ ($1 \le Q \le 150\,000$)가 주어진다.

$Q$개의 줄에 걸쳐, 도깨비가 하는 행동이 순서대로 "query $x$ $L$" 또는 "ad-hoc $k$ $L$" 형식으로 주어진다. 도깨비가 행동을 하려는 시점에서 혹부리 영감에게 달려 있는 혹의 개수를 $M$이라고 하자.

• "query $x$ $L$": $x$번 혹의 아래쪽 끝에서 시작해 혹을 따라 $L$만큼 거슬러 올라갔을 때 어떤 혹이 있는지 대답해야 한다. 그 지점이 두 혹의 경계라면 위쪽 혹의 번호를 답한다. 이때의 답이 지금부터의 "마지막 정답"이 된다. ($0 \le x < M$, $1 \le L \le 10^{18}$)
• "ad-hoc $k$ $L$": $x = (k +$ "마지막 정답"$) \mod M$ 을 계산한 후, 길이가 $L$인 $M$번 혹을 새로 만들어 $M$번 혹의 윗부분이 $x$번 혹의 아래에 닿도록 붙인다. $M$번 혹을 붙일 때에는 $x$번 혹 이외의 다른 혹에는 닿지 않게 한다. 아직 한 번도 query가 주어지지 않았다면 "마지막 정답"은 $0$으로 간주한다. 도깨비가 하는 모든 ad-hoc에서 주어지는 모든 $L$의 합은 $10^{18}$ 이하이다. ($0 \le k < M$)

항상 하나 이상의 query가 주어진다.

모든 query의 답을 순서대로 한 줄에 하나씩 출력한다.