Вам дано чисел a_1, a_2, \ldots, a_n. Ви маєте обробити запитів наступних двох видів:
: Додайте до кожного числа
: Знайдіть -те за величиною число (наприклад, якщо k = 1, знайдіть найбільше за величиною число)
Перший рядок містить два цілих числа (1 \le n, q \le 2\cdot 10^5) — кількість чисел та кількість запитів відповідно.
Другий рядок містить чисел a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — початкові значення чисел. Далі йде рядків, що описують запити.
Якщо запит першого типу, то відповідний рядок містить число та число (1 \le x \le 10^9). Інакше відповідний рядок містить число та число (1 \le k \le n).
Гарантується, що серед запитів принаймні один буде другого типу.
Для кожного запиту другого типу виведіть -те за величиною число.
Приклад 1
Запит 1: -ше число в масиві за величиною — .
Запит 2: Ми додаємо до всіх чисел. Тепер вони рівні 1000042, 1000001, 1000002.
Запит 3: -ге число в масиві за величиною — .
Запит 4: Ми додаємо до всіх чисел. Тепер вони рівні 1002064, 1002023, 1002024.
Запит 5: -тє число в масиві за величиною — .