571. Insert Nodes in Tree

0

Easy

Given the root of a binary tree, a value v, and a depth d, you are required to insert a row of nodes with the value v at the specified depth d. The root node is considered to be at depth 1.
The insertion rule is as follows: for a positive integer depth d, for each non-null tree node N at depth d-1, create two tree nodes with the value v as the root of the left and right subtrees of N. The original left subtree of N should become the left subtree of the new left subtree root, and the original right subtree of N should become the right subtree of the new right subtree root. If the depth d is 1, which means there is no depth d-1, then create a tree node with the value v as the new root of the entire original tree, and the original tree becomes the left subtree of the new root.

The given depth d is within the range of [1, maximum depth of the given tree + 1].

The given binary tree has at least one tree node.

**Note:**The given depth d is within the range of [1, maximum depth of the given tree + 1].

The given binary tree has at least one tree node.

Input Format

Enter the values of all the nodes in the binary tree in pre-order format, where 'true' indicates the existence of a node and 'false' indicates it is NULL.

Enter the values of v and depth d.

Enter the values of v and depth d.

Output Format

Display the tree after the addition of nodes.

Example

Input

4 true 2 true 3 false false true 1 false false true 6 true 5 false false false
10 2

Output

10 <- 4 -> 10
2 <- 10 ->
3 <- 2 -> 1
<- 3 ->
<- 1 ->
<- 10 -> 6
5 <- 6 ->
<- 5 ->

Constraints

**None**

**Loading...**

**View Submissions**

**Console**