Азир во својата слаткарница има N различни вкусови на сладоледи. Тој е решен денес да покаже колку брзо може да одговори на барањата на муштериите и да направи N сладоледи (означени со броевите од 1 до N). Се разбира, за да е поинтересно, секој од N-те муштерии ќе може да си нарача сладолед базирано на веќе претходно направените сладоледи. За да може да започне постапката, да претпоставиме дека Азир веќе „има“ еден „нулти“ сладолед (означен со 0) кој се состои само од корнет и на него нема ставено ниту едно топче.

Понатаму, i-тиот муштерија ќе одбере еден од претходно направените сладоледи (како шаблон), со реден број v, и може да зададе едно од следните барања:
a. Направи ми сладолед како v-тиот (v<i) и додај топче со вкус i одозгора (најгоре)
b. Направи ми сладолед како v-тиот (v<i) ама без најгорното топче. Кажи каков вкус беше тоа топче!
c. Направи ми сладолед како v-тиот (v<i). Кажи ми колку вкусови во мојот сладолед се исти со вкусовите кои ги има во сладоледот t (t<i)!

Новонаправениот сладолед е означен со i.

Азир ќе ги прави сладоледите, ама не сака да одговара на прашањата од муштериите. Направете програма која за барањата од тип b) и барањата од тип c) ќе ги отпечати одговорите на прашањата.

Влез

Во првиот ред е запишан цел број N (1 ≤ N ≤ 300 000), бројот на вкусови на сладоледи, т.е. бројот на муштерии, т.е. бројот на направени сладоледи. Сите муштерии (и сладоледи) се хронолошки означени со првите N цели броеви.

i-тиот од следните N редови содржи опис на барањето на i-тиот муштерија во една од следните 3 форми:
• „a v“ за барање од тип a.
• „b v“ за барање од тип b.
• „c v t“ за барање од тип c.

Првиот знак го означува типот на барањето, а следниот (или следните два броја) ќе ги означат соодветните претходно направени сладоледи – броеви од интервалот [0, i − 1]. За секое барање од тип b, сладоледот на кој ќе се повика муштеријата ќе има барем едно топче.

Излез

За секое барање од тип b или c отпечатете го бараниот број, по еден во ред, по редослед како што се поставени барањата.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6
a 0
a 1
b 2
c 2 3
b 4
a 1

излез
2
1
2

Објаснување на првиот тест пример: На почетокот „има“ „почетен” или “нулти“ сладолед без топчиња (само корнет) S0 = {}. Во првото барање Азир го копира S0 (корнетот) и додава топче со вкус 1 одозгора, па S1 = {1}. Во второто барање Азир го копира S1 и става топче со вкус 2 одозгора па S2 = {1, 2}. Во третото барање Азир го копира S2, но без најгорното топче (2) на него, па S3 = {1}, а одговорот на прашањето е 2.
Во четвртото барање Азир го копира S2 и се добива S4, па за да го одговориме прашањето ги броиме вкусовите кои се исти во S4 и во S3. Единствениот таков вкус е 1 па одговорот е 1. Во петтиот чекор Азир го копира S4, но без најгорното топче (2), па S5 = {1}. Одговорот на прашањето сега е 2.
Во шестото барање Азир го копира S1 и става топче со вкус 6 одозгора па S6 = {1, 6}.