Shoes
Лятна Информатическа Школа, 2009
Time Limit: 0.3s, Memory Limit: 64MiB
Много цивилизации са се сблъсквали така наречения "обувчен проблем". И докато хората на планетата Земя още не са проклела нозете си и не са почнала да летят, обувките си остават сериозен проблем, поне в средите на Елеонора.

Както всеки от вас сигурно знае, крайно недопустимо e две (или повече) момичета в училище да ходят с еднакви дрехи, прически или обувки. За това намирането на съответните аксесоари изобщо не е толкова лесна задача – ако Ели определи някакъв коефициент колко ѝ харесва даден чифт обувки (висок ток, по възможност дънките да могат да влязат вътре и т.н.), то не винаги е изгодно за нея да взима тези с най-високата стойност (например ако някое момиче в училището й вече си е взела същия модел). За това, когато тя прави шопинг между две пресечки на централната улица, момичето би искало да знае не само стойността на най-хубавите обувки, а стойностите на десетте най-хубави чифта!

Разбира се, обувките не са константа величина (зависими са от различни фактори като финансовата криза или пък от това каква част от тях са изкупени за костюмите на националния отбор по информатика (не твърде значим фактор, имайки предвид, че мнозинството предпочитат да носят костюма си с чехли). В даден момент е възможно на някоя улица да се получи нова доставка с обувки със, съответно, нова оценка спрямо критериите на Ели.

Помогнете на Ели като напишете програма, която отговаря на следните заявки:
  1. query A B – намира десетте (ако има толкова, иначе колкото има) най-добри стойности на обувки между пресечките A и B, включително.
  2. insert A V – добавя на пресечка A обувки с оценка V.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N - колко пъти са доставяли обувки или Ели е отивала на шопинг. Следват N реда, всеки описващ едно явление в зададения по-горе формат.
Изход
За всяка заявка с тип "query" изпечатайте по един ред с до десет числа - най-добрите стойности на обувки, които се предлагат в зададения интервал [A, B].
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ AB ≤ 100,000
  • -1,000,000,000 ≤ V ≤ 1,000,000,000
Примерен Вход Примерен Изход
16 insert 5 42 insert 7 13 query 1 6 query 42 42 query 5 7 insert 13 18 insert 13 19 insert 13 20 insert 13 1 query 1 100000 insert 16 15 insert 13 666 insert 50 50 insert 98765 43210 insert 13 19 query 1 100000 42 42 13 42 20 19 18 13 1 43210 666 50 42 20 19 19 18 15 13
Мрън!