Problem
Sebaik sahaja Konstantin, setelah mengambil bahagian dalam Olimpik antarabangsa ke-13 yang seterusnya, telah pulang dengan kereta api. Dia, seperti biasa, duduk dan berfikir tentang erti kehidupan, pada masa yang sama menyelesaikan masalah pengaturcaraan. Selepas beberapa lama, Konstantin tertidur, tetapi masalahnya ialah, untuk bangun, dia mesti menyelesaikan masalah yang timbul di kepalanya, yang menghantuinya!
Kali ini, Konstantin mengimpikan sebatang pokok yang pada mulanya hanya terdiri daripada satu bucu dengan nombor 1. Dalam masalah yang dia tetapkan, bucu baru ditambah secara beransur-ansur pada pokok itu. Dalam detik ke-i, bucu dengan nombor i+1 telah ditambahkan pada pokok itu, yang digantung sebagai anak daripada bucu p
i dan di tepi antara bucu i+1 dan p
i huruf c
i telah ditulis.
Setiap laluan dari akar pokok ke bucu v sepadan dengan rentetan tertentu yang diperoleh dengan menulis simbol yang ditulis di tepi laluan semasa dalam susunan dari akar ke bucu v. Konstantin menghadapi tugas yang sukar pada pandangan pertama - selepas setiap penambahan bucu baharu, kira bilangan rentetan unik bermula pada akar pokok (nombor bucu 1) dan berakhir pada beberapa bucu lain.
Dalam mimpinya, Konstantin bukanlah seorang genius sama sekali, jadi dia sendiri tidak dapat menyelesaikan masalah ini. Bantu Konstantin menyelesaikan masalah dan bangun.
Input:
Baris pertama mengandungi nombor n - bilangan permintaan untuk menambah nod baharu pada pokok (1 <= n <= 300000).
N baris seterusnya menerangkan permintaan untuk menambah bucu. Pertanyaan ke-i diterangkan oleh parameter p
i (1 <= p
i <= i) dan c
i, yang bermakna bucu yang ditambah dengan nombor i+1 digantung daripada bucu dengan nombor p
i sebagai kanak-kanak, dan simbol c
i ditulis pada tepi yang terhasil - huruf kecil abjad Latin.
Output:
Cetak n baris. Pada baris ke-i cetak jawapan kepada masalah Konstantin selepas menambah bucu ke-i+1.
Contoh:
| Input |
Output |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |