#P40046. 2020 GCPC A - Adolescent Architecture

2020 GCPC A - Adolescent Architecture

题目描述

Little Peter is building a stack out of his toy blocks. He is using two kinds of blocks -- cubes and cylinders -- and wants to stack all of them into a single tower, where each block other than the topmost block has a single block standing on it. In order for the tower to be stable, the outline of each block needs to be fully contained within the outline of the block below when looking at the tower from above (the outlines are allowed to touch). Is it possible to construct such a tower, and if so, in which order do the blocks need to be stacked?

输入格式

One line with an integer nn (1n1001 \le n \le 100), the number of blocks. nn lines, each with the description of a block. The description consists of a string giving the type of block (cube or cylinder) and an integer aa (1a10001 \le a \le 1\,000) giving the size of the block -- if the block is a cube then aa is its side length, and if it is a cylinder then aa is the radius of its base (note that the height of the cylinder does not matter).

输出格式

If there is no way to construct the tower, output impossible. Otherwise output nn lines, giving the order in which to stack the blocks from top to bottom.

样例

样例输入 1

3
cube 7
cube 11
cylinder 5

样例输出 1

cube 7
cylinder 5
cube 11

样例输入 2

2
cube 5
cylinder 3

样例输出 2

impossible

样例输入 3

3
cube 4
cylinder 2
cube 4

样例输出 3

cylinder 2
cube 4
cube 4