В первой строке задано целое число $n$ ($1 \le n \le 10^5$) --- количество элементов массива.

Во второй строке через пробел заданы $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$) --- элементы массива.

В третьей строке задано целое число $q$ ($1 \le q \le 10^5$) --- количество запросов.

В следующих $q$ строках заданы запросы по одному в строке. Запросы бывают трех видов:

\begin{itemize}
\item $1$ $k$ ($2 \le k \le 10^5$) --- запрос первого типа.

\item $2$ $k$ ($2 \le k \le 10^5$) --- запрос второго типа.

\item $3$ $l$ $r$ ($1 \le l \le r \le n$) --- запрос третьего типа.
\end{itemize}
