Given a binary tree, write a program to invert the binary tree and return it.

Example

Input:
     5
   /   \
  2     8
 / \   / \
1   4 6   9
Output:
     5
   /   \
  8     2
 / \   / \
9   6 4   1