İkili axtarış ağacı 2

Giriş

Giriş faylı, ağac üzərində icra ediləcək əməliyyatların təsvirini ehtiva edir və bu əməliyyatların sayı 100000-i keçmir. Əməliyyatların formatı ilə bağlı ətraflı məlumatı əvvəlki məsələdə tapa bilərsiniz. Hər bir sətirdə aşağıdakı əməliyyatlardan biri yer alır:

• insert x - x açarını ağaca əlavə edin. Əgər x açarı artıq ağacda varsa, heç bir əməliyyat etməyin.

• delete x - x açarını ağacdan silin. Əgər x açarı ağacda yoxdursa, heç bir əməliyyat etməyin.

• exists x - Əgər x açarı ağacda varsa, "true" çıxarın, əks halda "false".

• next x - Ağacda x-dən böyük olan ən kiçik elementi çıxarın və ya belə bir element yoxdursa, "none" çıxarın.

• prev x - Ağacda x-dən kiçik olan ən böyük elementi çıxarın və ya belə bir element yoxdursa, "none" çıxarın.

• kth k - k-cı böyüklükdə elementi çıxarın (nömrələmə birlə başlayır). Əgər belə bir element yoxdursa, "none" çıxarın.

Giriş faylındakı bütün rəqəmlər tamdır və modulu 10^9-u keçmir.

Çıxış

Bütün exists, next, prev əməliyyatlarının icrasının nəticələrini ardıcıl olaraq çıxarın. Nümunə çıxış faylının formatına əməl edin.

Nümunələr