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. 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.

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