Convert the BST to a Linked List

Given a binary search tree, you are asked to convert it to a linked list. Yet, we would still like to be able to search elements in the BST, so the elements in the linked list should be in increasing order.

Input

The input is handled automatically, you don’t need to do anything. It’s guaranteed that the input binary tree is valid.

Output

The program should return the root of the linked list.

Examples

Input
Output
7 3 1 2 4 7 3 2
1 2 2 3 3 4 7

Explanation

 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue