Studio Splice Tree Sample Lookup

A recording studio's non-linear editor never stores a finished track as one long buffer of encoded samples. Instead it keeps the track as a binary splice tree: every node is either a leaf holding a short literal run of encoded samples (written as lowercase letters), or an internal splice node whose output is defined as "play everything the left child produces, then everything the right child produces." Given such a splice tree and a list of sample positions, determine — for each queried position — which character sits there in the fully assembled track, without ever having to splice the whole track together.

Input format

• The first line contains a single integer n, the number of nodes in the tree. Nodes are indexed 0 to n-1, and node 0 is the root.
• Each of the next n lines describes node i (in index order) in one of two forms:
  • L s — a leaf whose literal snippet is the non-empty lowercase string s (no spaces).
  • N l r — an internal splice node whose left and right children are nodes l and r (0 <= l, r < n). It is guaranteed the nodes form a valid binary tree rooted at node 0: every node other than the root is the child of exactly one other node, leaves have no children, and internal nodes have exactly two children.
• The next line contains a single integer q, the number of queries.
• The last line contains q integers k_1 ... k_q, each a 1-indexed position into the fully assembled track (1 <= k_i <= the length of the track produced by the root).

Output format

Print a single line containing the q answer characters concatenated together, one per query, in the order the queries were given.

Constraints

• 1 <= n <= 10000
• The total length of all literal snippets combined is at most 100000.
• 1 <= q <= 10000
• 1 <= k_i <= (length of the track produced by the root), for every query

5
N 1 2
L ab
N 3 4
L cd
L ef
3
1 4 6

adf

1
L hello
2
1 5

ho