Tom, COMP1511's Course Administrator, has started a new business -- laying internet pipes for the NBN. The pipes have already been laid out in sections side by side, but they have arrived out of order and so they aren't connected properly. He wants to rearrange them into an order where they connect, and are as long as possible. When you have implemented this question, you will be able to take an input like this: | | \ / | | | | | III 11 11 And turn it into an output like this: | \ / | LIINT \ 1 X 1 / \\ \ \ LIIN You can do this by following the rules described below... Pipes and Connections There are three types of pipes: (the "straight" pipe) this pipe connects from the pipe above, to the pipe below. ./ (a "left" pipe) this pipe connects from the pipe above, to one space diagonally down and left. 1 (a "right" pipe) this pipe connects from the pipe above, to one space diagonally down and right. Pipe Rows and Ordering Each line of standard input will be a section of pipes. You cannot edit any of these lines, but you will need to change the order that they are printed out so that they connect correctly to the pipes above them. The first line of standard input will always be the first section of pipes and must be printed out first. After the first line, you should print them out the rest of the lines so that as many pipes as possible connect to the pipes above, and so that the pipes go on as long as possible. Order the rows so that the following rules are followed: 1. The next section of pipe must not ever contain a pipe that the previous section doesn't connect to. 2. If multiple sections of pipe could come next, the next section should maximize the number of pipes that continue from the last section. 3. If multiple sections of pipe could still come next, the next section should have as many straight pipes as possible. 4. If multiple sections of pipe could still come next, the section of pipe that was described earliest on standard input should be used. 5. If no sections of pipe could come next, end your program. Restrictions If a left pipe is in the left-most space, that pipe ends there. If a right pipe is in the right-most space, that pipe ends there. You are guaranteed that each line will be equally long, and no line will be longer than 1000 characters. You are guaranteed that there will be no more than 1000 lines. The only characters that will appear on a line will be the three pipe characters or space. Lines will end with a newline.