class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def get(self):
        return self.val

    def set(self, val):
        self.val = val

    def getChildren(self):
        children = []
        if (self.left != None):
            children.append(self.left)
        if (self.right != None):
            children.append(self.right)
        return children


class BST:
    def __init__(self):
        self.root = None

    def setRoot(self, val):
        self.root = Node(val)

    def insert(self, val):
        if (self.root is None):
            self.setRoot(val)
        else:
            self.insertNode(val)

    def insertNode(self, val):
        curr = self.root
        while True:
            if val >= curr.val:
                if curr.right is None:
                    curr.right = Node(val)
                else:
                    curr = curr.right
                    continue
            if val < curr.val:
                if curr.left is None:
                    curr.left = Node(val)
                else:
                    curr = curr.left
                    continue
            break

    def find(self, val):
        if self.root is None:
            return False
        curr = self.root
        while True:
            if val == curr.val:
                return True
            if val > curr.val:
                if curr.right is None:
                    return False
                else:
                    curr = curr.right
                    continue
            if val < curr.val:
                if curr.left is None:
                    return False
                else:
                    curr = curr.left
    def turnleft(self, val):
        if self.root is None:
            return None
            curr = self.root
        if self.root.left is None and self.root.right is None:
            return None
        curr = self.root
        while True:
            if val == curr.val:
                break
            if val > curr.val:
                if curr.right is None:
                    return False
                else:
                    curr = curr.right
                    continue
            if val < curr.val:
                if curr.left is None:
                    return False
                else:
                    curr = curr.left
        v1 = curr
        curr = curr.right
        v2 = curr.left
        curr.left = v1
        curr.left.right = v2


    def turnright(self, val):
        if self.root is None:
            return None
            curr = self.root
        if self.root.left is None and self.root.right is None:
            return None
        curr = self.root
        while True:
            if val == curr.val:
                break
            if val > curr.val:
                if curr.right is None:
                    return False
                else:
                    curr = curr.right
                    continue
            if val < curr.val:
                if curr.left is None:
                    return False
                else:
                    curr = curr.left
        v1 = curr
        curr = curr.left
        v2 = curr.left
        curr.right = v1
        curr.right.left = v2