Запаси на зиму

Вхідні дані

У першому рядку записано число $N$ — кількість банок, які є у Аліни, $(N \leq 1 0^{5})$ (N \le 10^5).

У другому рядку через пробіл задано $N$ чисел — якості яблук у відповідних банках.

У наступному рядку міститься число $M$ — кількість запитів до машини $(M \leq 5 \cdot 1 0^{5})$ (M \le 5 \cdot 10^5).

У кожному з наступних $M$ рядків описано один із двох запитів:

$L, R$ — відрізок, який розвертається $(0 \leq L < R \leq N - 1)$ (0 \le L < R \le N - 1).
$X$ — запит на якість яблук на позиції $X$ $(0 \leq X \leq N - 1)$ (0 \le X \le N - 1).

На кожен запит другого типу виведіть відповідь в окремому рядку.

Приклад 1

Loading