8.8 Build a Cake
(RankList for this Question)
Score: 60pts
Time Limit: 1.00 sec
Raju works in a bakery and a customer has come with a very specific request that they want the tallest cake. Raju decides that he will stack all of the available cakes on top of each other to make the tallest cake. He has different cakes of different width, depth and height but there is a problem if he stacks a cake of larger dimension (width, depth or height) than any other cake below it, then the cake will topple and he will lose his job. Help him make this cake !

Note that the cakes aren’t necessarily cylindrical in nature

Constraints
\(1 \leq \) number of cakes \( \leq 1000\)
\(1 \leq \) width \( \leq 100\)
\(1 \leq \) depth \( \leq 100\)
\(1 \leq \) height \( \leq 100\)

Input Format
The first line of the input contains the number of cakes
The n lines which follow contain the width, depth and height of each of the cakes.

Output Format
Output the array of cakes in the final stack, starting with the top cake and ending with the bottom cake.
The integers in each line must represent [width, depth, height] of the cake.

Example 1
Input:
3
2 1 2
3 2 3
2 3 4

Output:
2 1 2
3 2 3

Explanation:
Case 1: If [2, 3, 4] is considered for the base then no other cake can be stacked on top of it since every other cake’s width, depth and height is not less than 2, 3, 4 respectively.
For example [3, 2, 3] cannot be stacked on top of [2, 3, 4] because the width of [3, 2, 3] is larger than the width of [2, 3, 4].

Case 2: If [2, 1, 2] is considered (same reason as Case 1).

Case 3: If [3, 2, 3] is considered for the base then [2, 1, 2] can be stacked on top of it since each of its dimensions is less than [3, 2, 3]. The resulting stack has the highest total height.

Example 2
Input:
1
2 1 2

Output:
2 1 2

Explanation:
There is only one cake so it has to be the tallest stack.

Log In to solve the Question