Drawing a Modified Full Binary Tree

A binary tree is a basic data structure that is either empty or composed of a root node, a left subtree, and a right subtree; both subtrees are in turn binary trees. A full binary tree of height \(m-1\) has \(m\) levels (level 1 being the root level and level \(m\) the leaf level), where every level except the last is completely filled and all leaves are in the last level.

This problem requires you to draw a binary tree that is obtained from a full binary tree by deleting several nodes. The drawing rules for a full binary tree are as follows:

1. Each node is represented by the lowercase letter o. For each parent node, the connection to its left subtree is drawn using / and to its right subtree using \ (a single backslash).
2. Let \([i,j]\) denote the character in the \(i\)th row and \(j\)th column. If \([i,j]\) contains /, then both \([i-1,j+1]\) and \([i+1,j-1]\) must be either o or /. If \([i,j]\) contains \, then both \([i-1,j-1]\) and \([i+1,j+1]\) must be either o or \. Similarly, if \([i,j]\) in any of the first \(m-1\) levels (i.e. an internal node) is o, then \([i+1,j-1]\) must be / and \([i+1,j+1]\) must be \ (the branch connections to its left and right children).
3. For the \(m\)th level (the leaves): if two adjacent nodes belong to the same parent, then they are separated by exactly 3 spaces; if they are adjacent but do not share the same parent then they are separated by 1 space. The leftmost leaf has no leading space.

After drawing the full binary tree, you must delete \(n\) nodes. Deleting a node means replacing the printed characters of that node, all of its descendants (i.e. the entire subtree rooted at that node) and the connecting branch from its parent (if any) with space (ASCII 32). Note that deletions are performed on the originally drawn full binary tree.

Tree Drawing Details:
Assume the tree has \(m\) levels. The drawn output will have 2m-1 rows: the node rows are odd-numbered (row 1 for level 1, row 3 for level 2, …, row \(2m-1\) for level \(m\)), and the branch-connecting rows are even-numbered. The horizontal positions (columns) for the nodes are computed as follows:

• Leaf positions (level \(m\)): There are \(2^{m-1}\) leaves. Define their positions from left to right as follows: set the leftmost leaf at column 0. Then for each consecutive leaf index (0-indexed), if the current index is even (i.e. its sibling is next), add 4 (a letter and 3 spaces) to get the next sibling’s position; if the current index is odd (i.e. between different parents), add 2 (a letter and 1 space) to get the next leaf’s position.
• Internal node positions (levels 1 to \(m-1\)): For any internal node, its horizontal position is the integer average (i.e. \(\lfloor (x_{left}+x_{right})/2 \rfloor\)) of its two children’s positions.

Input and Deletion:
The input begins with two integers \(m\) and \(n\) representing the number of tree levels and the number of nodes to delete. The tree is a full binary tree with levels numbered 1 (root) to \(m\) (leaves). Then follow \(n\) lines, each containing two integers \(i\) and \(k\), indicating that the \(k\)th node (from the left, 1-indexed) at level \(i\) should be deleted. Deleting a node removes that node, its entire subtree, and the branch connecting it with its parent.

Output: Print the final drawing of the tree using the above rules. Any character removed by deletion should be replaced by a space (ASCII 32).

inputFormat

The first line contains two integers \(m\) (the number of levels, \(m \ge 1\)) and \(n\) (the number of deletion operations).
Each of the following \(n\) lines contains two integers \(i\) and \(k\), representing that the \(k\)th node on the \(i\)th level (1-indexed) is to be deleted, along with its entire subtree.

Note: If \(n = 0\) then no deletion is performed and the full binary tree is drawn.

outputFormat

Output the final drawing of the tree. The drawing consists of 2m-1 rows and a number of columns determined by the computed positions of the nodes. Each row should be printed exactly as drawn, with the nodes and branch characters placed according to the rules, and deleted parts replaced by spaces.

sample

2 0

  o  
/ \ 
o   o