You are given the root node of a binary tree.Print its preorder traversal.

Input Format:

The first and the only line of input will contain the node data, all separated by a single space. Since -1 is used as an indication whether the left or right node data exist for root, it will not be a part of the node data.

Output Format:

The only line of output prints the preorder traversal of the given binary tree.

Constraints:

1 <= N <= 10^6
Where N is the total number of nodes in the binary tree.

Time Limit: 1 sec