BST-ում (Փնտրման Բինար ծառ) ամենափոքր k արժեքների գումար գտնել

Տրված է դատարկ Փնտրման Բինար ծառ (BST), որտեղ նախնական որևէ արժեք ներմուծված չէ։ Ձեզ խնդրում են իրականացնել երկու տեսակ հարցում.

  1. insert xx-ի ներդնում BST-ում

  2. sum k – տպել BST-ում առկա ամենափոքր k արժեքների գումարը

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով q հարցում, պետք է հետևաբար կատարի վերը նշված գործողությունները։

Մուտք

Մուտքի առաջին տողում տրված է q ամբողջ թիվը (1 ≤ q ≤ 1000)։

Հաջորդ q տողերը պարունակում են հարցումները։ Բոլոր insert հարցումներում x-ի արժեքը բացարձակ արժեքով չի գերազանցում 10^9-ը։ Բոլոր sum հարցումներում k-ի արժեքը չի գերազանցում ծառում առկա տարրերի քանակը։

Ելք

Յուրաքանչյուր sum k հարցման համար ծրագիրը պետք է տպի BST-ում առկա ամենափոքր k արժեքների գումարը։

Օրինակներ

Մուտք

Ելք

8
insert 2
insert 1
sum 1
sum 2
insert 10
insert 20
sum 3
sum 2

1
3
13
3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue