Ağac
Kök ağacını nəzərdən keçirək. Başlanğıcda ağac yalnız bir kökdən ibarətdir. Hər bir zirvənin oğulları üçün soldan sağa doğru sıra müəyyən edilir. Ağac üzərində icazə verilən əməliyyatlar bunlardır:
Ağaca yarpaq əlavə etmək.
Ağacdan yarpaq silmək.
İki yarpaq arasında yolda olan zirvələrin sayını tapmaq.
İki yarpaq arasında "yol altı" zirvələrin sayını tapmaq.
u və v yarpaqları arasında "yol altı" zirvələr dəsti aşağıdakı kimi müəyyən edilir. Onların arasındakı u=w_0-w_1-...-w_k=v yolunu nəzərdən keçirək. Bu yolda hər iki kənarın oğullarına doğru getdiyi w_c zirvəsini seçək. Qoy müəyyənlik üçün bu kənarlardan sol tərəfdəki bizi u zirvəsinə, sağ tərəfdəki isə v zirvəsinə yaxınlaşdırsın. Onda "yol altı" olan zirvələr aşağıdakı kimi elan edilir:
w_{c-1} və w_{c+1} arasında yerləşən w_c zirvəsinin bütün oğulları və onların alt ağaclarının bütün zirvələri;
i = 1, 2, ..., c-1 üçün - w_{i-1} zirvəsinin oğulundan sağda yerləşən bütün w_i zirvəsinin oğulları və onların alt ağaclarının bütün zirvələri;
i = c+1, c+2, ..., k-1 üçün - w_{i+1} zirvəsinin oğulundan solda yerləşən bütün w_i zirvəsinin oğulları və onların alt ağaclarının bütün zirvələri.
Ağacı əlavə və silmə sorğularına uyğun olaraq yenidən quran və yol və "yol altı" zirvələrin sayını tapmaq üçün sorğulara cavab verən bir proqram yazın.
Giriş verilənləri
Giriş faylının ilk sətirində bir tam ədəd n - sorğuların sayı (0 ≤ n ≤ 300000) verilir. Növbəti n sətirdən hər biri bir sorğunu təsvir edir. Mümkün sorğu növləri bunlardır:
l x - yeni yarpağı x zirvəsinin ən sol oğulu kimi əlavə et.
r x - yeni yarpağı x zirvəsinin ən sağ oğulu kimi əlavə et.
a x y - yeni yarpağı x zirvəsinin oğulu kimi əlavə et, hansı ki, y zirvəsinin dərhal sağında yerləşir; y-dən sağda olan bütün x zirvəsinin oğulları əlavə edildikdən sonra yeni zirvənin sağında yerləşir; y zirvəsinin x zirvəsinin oğulu olduğu təmin edilir.
d x - x zirvəsini sil. Bu anda x zirvəsinin silinmədiyi və yarpaq olduğu təmin edilir.
p x y - x və y arasında, o cümlədən bu zirvələrin özləri də daxil olmaqla, yolda olan zirvələrin sayını tap; x və y yarpaqlar olduğu təmin edilir.
q x y - x və y arasında, o cümlədən bu zirvələrin özləri də daxil olmaqla, "yol altı" zirvələrin sayını tap; x və y yarpaqlar olduğu təmin edilir.
Əlavə edilən zirvələr sorğularda əlavə edildiyi ardıcıllıqla birdən nömrələnir. Ağacın kökü 0 nömrəsinə malikdir və heç bir zaman yarpaq hesab edilmir.
Çıxış verilənləri
Sorğuları ardıcıllıqla icra edərək, p və ya q növündən olan hər bir sorğuya cavabı ayrıca bir sətirdə yazın.