You are given a binary tree rooted at 1. You have to find the mirror image of any node q_i about node 1. If it doesn't exist then print -1.
Input:
First line of input is N and Q.
Next N-1 line consists of two integers and one character first of whose is parent node , second is child node and character "L" representing Left child and "R" representing right child.
Next Q lines represents q_i.
Output:
For each q_i print it mirror node if it exists else print -1.
NOTE: 1 is mirror image of itself.
Constraints:
1 <= N <= 10³
1<= Q <= 10³