[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:

(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++