from copy import copy, deepcopy


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

    def __copy__(self):
        new_node = Node(self.data)

        if self.left is not None:
            new_node.left = copy(self.left)

        if self.right is not None:
            new_node.right = copy(self.right)

        return new_node


    def __deepcopy__(self, memo):
        if id(self) in memo:
            return memo[id(self)]

        new_node = Node(self.data)

        memo[id(self)] = new_node

        new_node.left = deepcopy(self.left, memo)
        new_node.right = deepcopy(self.right, memo)

        return new_node


class BST:
    def __init__(self, values=None):

        self.root = None

        if isinstance(values, list):

            for value in values:

                if type(value) == int:
                    self.insert(value)

                else:
                    raise ValueError("BST chỉ nhận số nguyên")

        elif isinstance(values, str):

            value = None

            for x in values:

                if '0' <= x <= '9':

                    if value is None:
                        value = 0

                    value = value * 10 + (ord(x) - ord('0'))

                elif x == ' ' or x == ',':

                    if value is not None:
                        self.insert(value)
                        value = None

                else:
                    raise ValueError("Ký tự không hợp lệ")

            if value is not None:
                self.insert(value)


        elif values is None:
            self.root = None

        else:
            raise ValueError("Input không hợp lệ")

    def insert(self, value):

        self.root = self._insert(self.root, value)

    def _insert(self, node, value):

        if node is None:
            return Node(value)

        if value < node.data:
            node.left = self._insert(node.left, value)

        else:
            node.right = self._insert(node.right, value)

        return node

    def remove(self, value):

        self.root = self._remove(self.root, value)

    def _remove(self, node, value):

        if node is None:
            return None

        # tìm node cần xóa

        if value < node.data:

            node.left = self._remove(node.left, value)

        elif value > node.data:

            node.right = self._remove(node.right, value)

        else:

            # ===== CASE 1: node lá =====

            if node.left is None and node.right is None:
                return None

            # ===== CASE 2: có 1 con =====

            if node.left is None:
                return node.right

            if node.right is None:
                return node.left

            # ===== CASE 3: có 2 con =====

            successor = self._min(node.right)

            node.data = successor.data

            node.right = self._remove(node.right, successor.data)

        return node

    def _min(self, node):

        while node.left is not None:
            node = node.left

        return node

    def inorder(self):

        self._inorder(self.root)

        print()

    def _inorder(self, node):

        if node is None:
            return

        self._inorder(node.left)

        print(node.data, end=' ')

        self._inorder(node.right)

    def __copy__(self):

        new_bst = BST()

        if self.root is not None:
            new_bst.root = copy(self.root)

        return new_bst

    def __deepcopy__(self, memo):

        if id(self) in memo:
            return memo[id(self)]

        new_bst = BST()

        memo[id(self)] = new_bst

        new_bst.root = deepcopy(self.root, memo)

        return new_bst


    def __iter__(self):
        yield from self._iter_inorder(self.root)


    def _iter_inorder(self, node):

        if node is None:
            return

        yield from self._iter_inorder(node.left)

        yield node.data

        yield from self._iter_inorder(node.right)

    def __getitem__(self, key):

        values = list(self)

        if isinstance(key, slice):

            new_values = values[key]

            return BST(new_values)

        return values[key]
        
        
class vector3D(object):
	"""docstring for vector3D"""
	def __init__(self, x, y, z):
		super(vector3D, self).__init__()
		self.x = x
		self.y = y
		self.z = z
	
	def __str__(self):
		return f"[{self.x}, {self.y}, {self.z}]"

	def __add__(self, other):
		if isinstance(other, vector3D):
			return vector3D(self.x + other.x, self.y + other.y, self.z + other.z)
		else:
			return vector3D(self.x, self.y, self.z)

	def __radd__(self, other):
		return self.__add__(other)

	def __neg__(self):
		return vector3D(- self.x, - self.y, - self.z)

	def __mul__(self, other):
		if isinstance(other, vector3D):
			return (self.x * other.x) + (self.y * other.y) + (self.z * other.z)
		elif isinstance(other, (int, float)):
			return vector3D(self.x * other, self.y * other, self.z * other)
		else:
			return vector3D(self.x, self.y, self.z)

	def __rmul__(self, other):
		return self.__mul__(other)

	def __iter__(self):
		return iter(f"{self.x}{self.y}{self.z}")