# F005B. Russian dolls P96460

Statement

html

[r] The Russian dolls are a Russian souvenir that consist of a succession of dolls, of decreasing sizes, each (except the first) inside the previous one.

Your task is to write a program that, for each rectangle set given, decides if they are like Russian dolls, that is, if for each pair of rectangles one of them is inside the other.

The three first input instances correspond to the following figures. Only the one on the left is a Russian doll.

To solve this problem, you must use the following definition of rectangle:

int east, west, north, south; };

(For instance, the rectangle on the top and on the right has the values 25, 21, 9 and 2.)

Using this defition, you must implement and use the function

that indicates if the rectangle a is strictly included (that is, without equality in any of the coordinates) inside the rectangle b or it is not.

Input

The input consists of a sequence of cases separated with an empty line. Each case starts with a natural number n ≥ 1, followed by n rectangles with the sides parallel to the horizontal and vertical axes. Each rectangle is defined with four integer coordinates: east, west, north and south. In each case, there will not be horizontal or vertical coordinates repeated.

Output

For each case, if they are Russian dolls, your program has to print the rectangles from large to small. Otherwise, it has to print "They are not Russian dolls". Separate each output case with an empty line.

Observation

Your program has to be efficient. In particular, quadratic solutions in n will be rejected by the Judge or in the manual correction.

Public test cases
• Input

```3
8 1 9 1
5 3 6 5
6 2 7 4

4
19 10 8 1
16 15 5 4
12 11 6 2
18 13 7 3

2
24 23 9 2
25 21 5 3

1
8 -100 0 -100

2
3 2 1 0
102 100 3 2
```

Output

```8 1 9 1
6 2 7 4
5 3 6 5

They are not Russian dolls

They are not Russian dolls

8 -100 0 -100

They are not Russian dolls
```
• Information
Author
Professorat de P1
Language
English
Translator
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++