Problem : 219 - D. Tentacle Treeeeeeee

Problem Statistics

Solved Member: 17　　Submission: 60　　User Tried: 17

Statement:

觸手一隻非常強悍的生物，從一開始只有的一個節點，漸漸長出很多生節點，為了避免被攻擊，還會改變自己的頭部，隨機選擇一點節點當頭部，漫無目的的成長是一件很無聊的事，身為一隻觸手多少要有點娛樂，因此觸手每次都會問自己從節點V往頭部的方向走K個節點會到哪個節點。

你的任務是模擬一隻觸手，因此必須做到以下的操作：

1. "a u"表示從節點u的地方長出一個新的節點(一開始的節點編號1，第i次長的節點編號為i+1)。

2. "r u"表示將頭部位置改變至節點u。

3. "q u k"表示詢問從節點u開始，在u與頭部來回走共走K部後會抵達哪個節點。
i.e. 在點 u 和頭部兩點所形成的路徑上來回走動，若碰到頭部或點 u 時還有剩下的步數就折返

Input:Output:

每筆測試檔一筆測試資料。

第一行有一個數字n表示操作數(1 <= n <= 300000)，操作方法如題目敘述，保證不會有不合法操作。

為了保證大家寫在線做法，我們將對所有的輸入數字做上一點變化，我們將對所有的數字加上上次所需要輸出的數字d，若尚未輸出任何數字則d=0。所以要還原原本的數字你必須減掉上次所輸出的數字d。

對於每筆操作3輸出一個數字(佔一行)。

Sample Input:Sample Output:

Sample 1:
3
a 1
q 2 1
a 3

Sample 2:
10
a 1
a 2
q 2 1
q 2 2
a 3
q 4 2
r 6
q 5 3
q 5 4
q 5 6

Sample 1:
1

Sample 2:
1
1
2
2
4
4

HINT:

還原的測資：

Sample 1:
3
a 1
q 2 1
a 2

Sample 2:
10
a 1
a 2
q 2 1
q 1 1
a 2
q 3 1
r 4
q 3 1
q 3 2
q 1 2

對於40%的測試資料，1<=n<=5000。
對於70%的測試資料，1<=n<=100000。
對於100%的測試資料，1<=n<=300000。

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	2000ms	65536kb	10
10	2000ms	65536kb	10