8.8 Build a Cake

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

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\)

\(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.

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.

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.

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.

1

2 1 2

Output:

2 1 2

Explanation:

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