Problem D
Towers of Powers 2: Power Harder
Remark: We were originally planning to give you this in the real contest, but since we have too many awesome problems for you for tomorrow and this one is just way too easy, we decided to move it to the dress rehearsal as a sneak preview.
In this problem we will be exploring the concept of sorting numbers. Most of you have likely written a sorting algorithm before, but just in case, here is a tutorial: You reorder the numbers to put the smaller ones in front and larger ones in the back.
Having dealt with the theory, we come to practice. You will be given some integers. Please output the same integers in sorted order. Where is the trick, you ask? Well, you might have to deal with equality cases. If two numbers are equal, the one that was the first in the input should also be the first on the output. Other than that, there are no tricks, no complications. Just sort the numbers from lowest to highest. Simple!
Oh, one more thing. When we say some integers, we mean they might be somewhat large integers. To make life easier for you, we will express them in a simple “tower of powers” form. Each integer will be in the format
\[ a_1^{a_2^{\ldots ^{a_ n}}}, \]where $1 \leq a_1, a_2, \ldots , a_ n \leq 100$, and $1 \leq n \leq 100$. Note that evaluation is from top to bottom, thus
\[ a_1^{a_2^{a_3}} = a_1^{\left(a_2^{a_3}\right)}. \]Are you done yet? No? Better start working!
Input
The input consists of a single test case. The first line of each test case contains the number $M$ of integers in this test case, $1 \leq M \leq 100$. Each of the next $M$ lines describes one of the $M$ integers. The integer is written as described above, using the caret (^) to represent power, with no whitespace. There will be between $1$ and $100$ numbers in the representation of each integer, and each of these numbers will be an integer between $1$ and $100$.
Output
Display the case number ($1$) followed by the sorted list of integers, one per line, in the original form.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2^2^2 3^4 15 9^2 |
Case 1: 15 2^2^2 3^4 9^2 |