Write a program (again) to play with words. Your program should support the following commands.

• insert left x n Insert n characters of x at the beginning of a word.
• insert right x n Insert n characters of x at the end of a word.
• insert k x n Insert n characters of x so that the first of them will become the k-th character of this word.
• print
  Print the current content of the word in the following format: if the word is "gooooooooooooooooooooooooooogle", you should print "g 1 o 27 g 1 l 1 e 1 $". In other words, you should encode all consecutive sequences with the same character into character-length pairs, then print a dollar sign to indicate the end of the word.

Where x is a alphanumeric character and both n and k are positive integers.

Note that you need to implement this word as a binary tree, otherwise it it very likely that you will run out of time because you need to run through the data structure in order to find the correct location for insertion. You may want to store the number of characters in a node, as well as the number of characters in the subtree to speed thing up.