The array is given (its first, initial version). You must be able to answer two questions: \begin{itemize} \item \textbf{a_i\[j\]} = \textbf{x} - create the new version from \textbf{i}-th one, where the \textbf{j}-th element equals to \textbf{x}, and other elements are the same like in \textbf{i}-th version. \item \textbf{get a_i\[j\]} - print the \textbf{j}-th element in the \textbf{i}-th version. \end{itemize} \InputFile The size of array \textbf{n} (\textbf{1 }≤ \textbf{n }≤ \textbf{10^5}) and \textbf{n} elements of array. Then goes the number of queries \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{10^5}) and \textbf{m }queries themselves. The format is given in the sample input. If we have already \textbf{k }array versions, the new one gets the number \textbf{k + 1}. All array elements (old and new) are integers from \textbf{0 }to \textbf{10^9}. The array elements are numbered with integers from \textbf{1 }to \textbf{n}. \OutputFile For each \textbf{get} query print the corresponding element of the array.