Cookie Crumbs

Time limit1sMemory limit128 MB

Summary

Given a rectangle and up to 100 closed rectangular chips removed from it, count the connected crumbs left.

Level: Medium7 of 10
Topics: Geometry, Union-find, Combinatorics
Solved: No attempts yet

Problem

Cookie Monster bakes a rectangular cookie and studs it with rectangular chocolate chips. He turns the oven up too high, so every chocolate chip melts and leaks out, leaving a hole exactly where that chip sat. Once these holes appear, the cookie can break apart into several disconnected pieces, called crumbs.

Each chocolate chip is an axis-aligned rectangle and is treated as a closed region: it includes the points on its perimeter. As a result, two pieces of cookie that meet only at a single corner point count as separate crumbs, because that shared corner point is removed together with the chip.

Given the cookie and all of the chocolate chips, count how many crumbs remain after every chip melts away.

Input

The first line contains four integers x1 y1 x2 y2, each between $-10^9$ and $10^9$ , giving the coordinates of two opposite corners of the cookie. The cookie is an axis-aligned rectangle whose sides are parallel to the coordinate axes.

The second line contains an integer n with $0 \le n \le 100$ , the number of chocolate chips.

Each of the next n lines contains four integers x1 y1 x2 y2, each between $-10^9$ and $10^9$ , giving two opposite corners of one chocolate chip. Every chip is an axis-aligned rectangle.

Chips may overlap one another, and a chip may lie partly or entirely outside the cookie. The cookie and every chip have non-zero area. Each chip includes the points on its perimeter.

Output

Print a single integer: the number of crumbs (connected pieces) the cookie splits into once all of the chocolate chips have melted away.

Examples3

Example 1

Input

0 0 100 100
2
0 0 50 50
50 50 100 100

Expected output

Example 2
Input
```
0 0 10 10
0
```
Expected output
```
1
```
Example 3
Input
```
0 0 10 10
1
-5 -5 15 15
```
Expected output
```
0
```