In this project, you are supposed to implement a B+ tree of order 3, with the following operations: initialize, insert (with splitting) and search. The B+ tree should be able to print out itself.

Each input file contains one test case. For each case, the first line contains a positive number N (≤10​4​​), the number of integer keys to be inserted. Then a line of the N positive integer keys follows. All the numbers in a line are separated by spaces.

For each test case, insert the keys into an initially empty B+ tree of order 3 according to the given order. Print in a line Key X is duplicated where X already exists when being inserted. After all the insertions, print out the B+ tree in a top-down lever-order format as shown by the samples.

192