using System.CodeDom.Compiler;

using System.Collections.Generic;

using System.Collections;

using System.ComponentModel;

using System.Diagnostics.CodeAnalysis;

using System.Globalization;

using System.IO;

using System.Linq;

using System.Reflection;

using System.Runtime.Serialization;

using System.Text.RegularExpressions;

using System.Text;

using System;

​

class Solution {

    public class TreeNode {

        public int val;

        public TreeNode left_ptr;

        public TreeNode right_ptr;

        public TreeNode(int val){

            this.val = val;

            this.left_ptr = null;

            this.right_ptr = null;

        }

    }

​

    class BinaryTree {

       class Edge {

            public int parentNodeIndex;

            public int childNodeIndex;

            public string leftRightFlag;

        }

​

        private int noOfNodes;

        private int noOfEdges;

        private int rootIndex;

        private List<int> nodeValues;

        private List<Edge> edges;

        public TreeNode root;

​

        public BinaryTree(){

            this.noOfNodes = 0;

            this.noOfEdges = 0;

            this.rootIndex = -1;

            this.root = null;

            this.nodeValues = new List<int>();

            this.edges = new List<Edge>();

        }

​

        public void readRawValues(){

            noOfNodes = Int32.Parse(Console.ReadLine());

            if(noOfNodes > 0){

                string[] nodeValuesStringArray = Console.ReadLine().Split(' ');

                for(int i=0; i<noOfNodes; i++){

                    int val = Int32.Parse(nodeValuesStringArray[i]);

                    nodeValues.Add(val);

                }

            }

            rootIndex = Int32.Parse(Console.ReadLine());

            noOfEdges = Int32.Parse(Console.ReadLine());

            for(int i=0; i<noOfEdges; i++){

                string[] edgeStringArray = Console.ReadLine().Split(' ');

                Edge edge = new Edge();

                edge.parentNodeIndex = Int32.Parse(edgeStringArray[0]);

                edge.childNodeIndex = Int32.Parse(edgeStringArray[1]);

                edge.leftRightFlag = edgeStringArray[2];

                edges.Add(edge);

            }

        }

​

        public void buildFromRawValues(){

            if(noOfNodes == 0){

                root = null;

                return;

            }

            List<TreeNode> nodes = new List<TreeNode>();

            for(int i=0; i<noOfNodes; i++){

                nodes.Add(new TreeNode(nodeValues[i]));

            }

            for(int i=0; i<noOfEdges; i++){

                if(edges[i].leftRightFlag=="L"){

                    nodes[edges[i].parentNodeIndex].left_ptr = nodes[edges[i].childNodeIndex];

                }else{

                    nodes[edges[i].parentNodeIndex].right_ptr = nodes[edges[i].childNodeIndex];

                }

            }

            root = nodes[rootIndex];

        }

    }

​

    public static TreeNode readBinaryTree(){

        BinaryTree inputBinaryTree = new BinaryTree();

        inputBinaryTree.readRawValues();

        inputBinaryTree.buildFromRawValues();

        return inputBinaryTree.root;

    }

    /*

        public class TreeNode {

            public int val;

            public TreeNode left_ptr;

            public TreeNode right_ptr;

        }

    */

    /*

        Complete the function below

    */

    public static int maxLeftNodeVal = -10^9;

    public static int minRightNodeVal = 10^9;

    public static bool isBST(TreeNode root)

    {

         if(null == root)

         return true;

        return isBSTHelper(root, minRightNodeVal, maxLeftNodeVal);

    }

    public static bool isBSTHelper(TreeNode root,int min, int max){

​

        //DFS traversal

        if(null == root)

         return true;

      if(root.val < min || root.val > max)

       return false;

        return (isBSTHelper(root.left_ptr, min, root.val) &&  isBSTHelper(root.right_ptr, root.val, max));

    }

    public static void BFS(TreeNode root)

    {

        if(null == root)

         return;

         Queue<TreeNode> q = new Queue<TreeNode>();

        TreeNode n = null;

        q.Enqueue(root);

            while(q.Count != 0)

        {

              n = q.Dequeue();

            if(null != n.left_ptr)

             q.Enqueue(n.left_ptr);

              if( null != n.right_ptr)

              q.Enqueue(n.right_ptr);

              //Action

              //print node

        }

    }

​

​