4. Priority Trees

INPUT FILE: pritrees.in
OUTPUT FILE: none (to screen)

        2
       / \
    2       7
   / \     / \
  9   1   5   3
 / \     /     \
6   8   7       4

Priority Trees
A priority queue is a structure containing elements that each have a priority value associated with them. A priority tree is a special kind of binary tree in which each element has a higher element than its children.
The value of each node determines its priority, with 1 having the highest priority and 9 the lowest. If two nodes have the same value then they have the same priority. Your task will be to convert the given binary tree into a priority tree.
To do this, first search through the tree for the highest priority element and switch it with its parent (if it exists) and keep switching until it has reached the highest priority possible. Do this until all priorities are in their correct positions.

In our example we have

        2                    2                    1          
       / \                  / \                  / \         
    2       7            1       7            2       7      
   / \     / \    =>    / \     / \    =>    / \     / \   =>
  9   1   5   3        9   2   5   3        9   2   5   3    
 / \     /     \      / \     /     \      / \     /     \   
6   8   7       4    6   8   7       4    6   8   7       4  

        1                    1        
       / \                  / \       
    2       3            2       3    
   / \     / \    =>    / \     / \   
  9   2   5   7        9   2   5   4  
 / \     /     \      / \     /     \ 
6   8   7       4    6   8   7       7

Rotation
Once it has been converted, rotate the tree by the given angle and display it with the main root at the appropriate edge of the screen so that the whole tree fits on screen.

INPUT
The first line of input will consist of the angle, in degrees, of rotation (90 or -90).
The following lines will represent the binary tree (guaranteed to fit on a screen), followed by 2 blank lines.
The 2nd, 4th, 6th... lines consist of a string of digits from 1 to 9 representing nodes of the tree.
The 3rd, 5th, 7th... lines consist of a string of slashes (/ and \) representing connections between nodes, with blanks left where part of the tree is missing.

OUTPUT
Output to screen the rotated binary tree; each subtree must be displayed completely above/below and right/left of its parental node (depending on the direction of rotation).

Sample Input File

90
2
/\
27
/\/\
9153
/\bb/bb\
6874
(blank line)
(blank line)

Note: the "b"s represent spaces here for clarity and will not be in the input file.

Output for Sample Input

       7
      /
     4
    /
   3
    \
     5
      \
       7
 /
1
 \
    2
   /
  2
   \
      8
     /
    6
     \
      9