Description
There is a growing Binary Search Tree(gBST) in Hakka's village,
the gBST is original a binary search tree,
a binary search tree is rooted binary tree,
the value stored in each node is greater than any value stored in the left subtree,
and less than any value stored in the right subtree.
One night, the Hakka's found that the gBST growed larger,
some random values are added into the gBST, in random position.
In order to make gBST maintain a Binary Search Tree,
the Hakka's need to prune the tree.
And since Hakka's are frugal, they want the gBST to have as many nodes as possible.
To prune a node off the gBST, this node must be a leaf of the gBST,
a leaf of the tree is a node with no left subtree and no right subtree.
Every round of pruning, the Hakka's will prune all leaves that need to be removed,
until the gBST turns back to a binary search tree.
So before the pruning process start,
the Hakka's ask you to mark the node to 'negative X' if the node will be pruned at round X.
If the node will remain on the gBST, you don't need to mark the node.
ouo.
For Sample Input 1,
7
5 1 9 2 4 6 11
0 1L 1R 2L 3L 5L 3R
Input
Input contains 3 lines.
The first line contains an integer N, represent the number of nodes after gBST grows.
The second line contains N numbers Vi, represents the value stored on the node with index i.
The third line contains N strings Fi, Fi will be a number X concatenate with a letter 'L' or 'R',
the number X represents the parent node index of the ith node,
and the letter 'L' represents the ith node is the left child of index X node,
the letter 'R' on the other hand represents the ith node is the right child of the index X node.
If Fi = "0", the ith node is the root node.
The index of node is from 1 ~ N.
It's guarantee that:
1 <= N <= 10^5
1 <= Vi <= 10^9,
and the gBST is always a valid binary tree, with no duplictate values.
Output
Output contains only 1 line.
The line contains N numbers Xi,
represent the value of the node of index i on the gBST after you mark all nodes that need to prune.
With space between the number.
Remember to add a newline character at the end of the line.