A records office stores every document's call number in a binary search tree: for any node, every call number in its left subtree is strictly smaller than the node's own call number, and every call number in its right subtree is strictly larger. A clerk keeps a single cursor over this tree, positioned initially just before the smallest call number in the whole archive. The clerk repeatedly issues one of four commands: step forward to the next larger call number, step back to the next smaller one, or simply ask (without moving) whether stepping in either direction is currently possible. Process the clerk's commands in order and report the result of each one.

Input format

• Line 1: a single integer t, the number of tokens in a level-order (breadth-first) serialization of the tree, counting both value tokens and null placeholders for missing children.
• Line 2: t space-separated tokens. The first token is the root's call number. After that, treat the already-emitted nodes as a queue in the order they were introduced: for each node popped from that queue, its next unread token is its left child and the token after that is its right child, where each of those two tokens is either an integer or the literal null (meaning that child does not exist and is not pushed onto the queue).
• Line 3: a single integer q, the number of commands.
• Each of the next q lines contains exactly one command: NEXT, PREV, HASNEXT, or HASPREV.

Output format

Print q lines, one per command, in the order the commands were given:

• NEXT — move the cursor to the next larger call number and print it.
• PREV — move the cursor to the next smaller call number and print it.
• HASNEXT — print true if a NEXT move is currently possible, otherwise false. This never moves the cursor.
• HASPREV — print true if a PREV move is currently possible, otherwise false. This never moves the cursor.

It is guaranteed that a NEXT command is only ever issued when HASNEXT would currently report true, and a PREV command is only ever issued when HASPREV would currently report true. HASNEXT and HASPREV may be issued at any point, including before any move has been made, and must simply report the correct boolean.

Constraints

• 1 <= number of actual nodes in the tree <= 10^5.
• 0 <= every call number <= 10^6, and all call numbers in one tree are distinct.
• 1 <= q <= 10^5.
• The tokens always describe a tree that satisfies the binary-search-tree ordering property.

11
4 2 6 1 3 null null null null null null
6
NEXT
NEXT
HASPREV
PREV
HASNEXT
NEXT

1
2
true
1
true
2

1
7
3
HASNEXT
NEXT
HASNEXT

true
7
false