Запити#12874

Запити

1 second
256 megabytes
Very easy

Вам дано чисел a_1, a_2, \ldots, a_n. Ви маєте обробити запитів наступних двох видів:

Input

Перший рядок містить два цілих числа (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).

Гарантується, що серед запитів принаймні один буде другого типу.

Output

Для кожного запиту другого типу виведіть -те за величиною число.

Examples

Example 1

Loading
Loading

Note

  • Запит 1: -ше число в масиві за величиною  — .

  • Запит 2: Ми додаємо до всіх чисел. Тепер вони рівні 1000042, 1000001, 1000002.

  • Запит 3: -ге число в масиві за величиною  — .

  • Запит 4: Ми додаємо до всіх чисел. Тепер вони рівні 1002064, 1002023, 1002024.

  • Запит 5: -тє число в масиві за величиною  — .