Binary Search Tree Iterator

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from the $n$ distinct keys $a_1,a_2,\ldots,a_n$ in insertion order. Consider its inorder sequence: the keys obtained by visiting left subtree, root, then right subtree.

An iterator initially points to a position before the first element of this inorder sequence. Process $q$ commands in order:

N represents next(): move the iterator to the next inorder element and print that key.

H represents hasNext(): print whether an element still exists after the current iterator position. This command does not move the iterator.

Every N command is guaranteed to be valid, so at least one next element exists whenever N is issued.

Input

The first line contains $n$.

The second line contains the $n$ distinct keys $a_1,a_2,\ldots,a_n$.

The third line contains $q$.

Each of the next $q$ lines contains exactly one character, N or H.

Output

Every command produces exactly one output line.

For N, print the key returned by next().

For H, print lowercase true if a next element exists, otherwise lowercase false.

Subtasks

Subtask 1 (20 points): $1\le n,q\le 20$.

Subtask 2 (30 points): $1\le n,q\le 500$.

Subtask 3 (50 points): $1\le n,q\le 10^5$.

In all subtasks, $0\le a_i\le 10^6$, all $a_i$ are distinct, and every N command is valid.

Examples

Input

5
7 3 15 9 20
10
N
N
H
N
H
N
H
N
H
H

Output

3
7
true
9
true
15
true
20
false
false

Explanation

The inorder sequence is $3,7,9,15,20$. The first two N commands move to $3$ and $7$.

There is still a next element after $7$, so H prints true. Later N commands return $9$, $15$, and $20$. Once the iterator reaches $20$, no element remains, so the final two H commands both print false; calling H does not change the iterator position.