Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and an integer val.

Insert val into the BST such that the tree remains a valid BST. Return the root node of the BST after the insertion.

It is guaranteed that the new value does not exist in the original BST.

Example:

Input

root = [4,2,7,1,3]
val = 5

Output

[4,2,7,1,3,5]

Input

root = [40,20,60,10,30,50,70]
val = 25

Output

[40,20,60,10,30,50,70,null,null,25]