PROG0326 - Collision detection

no tags 

What does it mean for two objects to collide? This is an import question in many applications, which cannot always be answered easily by a computer program. If two planar objects overlap, this is called a collision. You should not take this too literally and immediately think about two cars that crashed against each other. Collision detection can be used for example to determine whether one region is contained within another region on a map, or to analyse images.

axis-aligned bounding box
The continental states of the US together with their respective axis-aligned bounding box.

For this exercise, we consider the simplest form of collision detection. In this, each object is represented by its axis-aligned bounding box. This is the smallest rectangle that contains the entire object and has edges parallel to the $X$- and $Y$-axis. We say that two objects collide if their bounding boxes overlap.

Input

The input contains eight integers (each on a separate line) that represent two diametrical points of two rectangles. Each point is described by two consecutive integers, with the first being the $x$ co-ordinate and the second the $y$ co-ordinate. The rectangles are real rectangles and are not degenerate as a line segment or a point.

Output

There is only one single line of output. This line contains the text collision if the two given rectangles overlap, and the text no collision if the two rectangles do not overlap. Note: touching rectangles do not overlap!

Example

Input:

0
0
1
2
4
1
5
5

Output:

no collision

Example

Input:

0
0
2
3
1
2
5
5

Output:

collision

Wat is de onderlinge positie van twee gegeven objecten? Het is een belangrijke vraag, die niet altijd even makkelijk te beantwoorden is door een computerprogramma. Als twee objecten in het vlak overlappen, dan noemen we dit een botsing. Je moet dit echter niet te letterlijk opnemen en direct denken aan twee auto's die elkaar aangereden hebben. Een botsing kan bijvoorbeeld ook gebruikt worden om te bepalen of twee onderdelen op een kaart in elkaar liggen, of om delen van foto's te analyseren.

axis-aligned bounding box
De continentale staten van de VS samen met hun respectievelijke axis-aligned bounding box.

Bij deze opgave gaan we een vereenvoudigde versie van het probleem bekijken. We stellen een object voor door zijn axis-aligned bounding box. Dit is de rechthoek die net het object omsluit en waarvan de zijden evenwijdig zijn met de $X$- en $Y$-as. We zeggen dan dat twee objecten botsen als hun bounding boxes overlappen.

Invoer

De invoer bestaat uit acht gehele getallen (één per regel) die tweemaal twee diametrale punten van twee rechthoeken voorstellen. Het eerste getal is telkens de $x$-coördinaat en het tweede getal de $y$-coördinaat. De rechthoeken zijn echte rechthoeken (en dus niet ontaard als lijnstuk of punt).

Uitvoer

De uitvoer bestaat uit één regel. Deze regel bevat de tekst botsing als de twee rechthoeken overlappen en de tekst geen botsing als de twee rechthoeken niet overlappen. Opgelet: raken is niet overlappen!

Voorbeeld

Invoer:

0
0
1
2
4
1
5
5

Uitvoer:

geen botsing

Voorbeeld

Invoer:

0
0
2
3
1
2
5
5

Uitvoer:

botsing


Added by:Peter Dawyndt
Date:2013-02-13
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None