Tree Traversal

You are given a tree root and a list of strings moves consisting of "RIGHT", "LEFT" and "UP". Starting from root, traverse the tree by performing each move in moves where:

• "RIGHT" means to traverse to the right child.
• "LEFT" means to traverse to the left child.
• "UP" means to traverse to its parent.

Return the value of the last node after all moves. You can assume that the moves are valid.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Tree-Traversal

Examples

Example 1

Input

• root =

• moves = ['RIGHT', 'RIGHT', 'UP', 'LEFT', 'RIGHT']

Output

• answer = 2

Solution