Rectangles and Shape

Time limit2sMemory limit128 MB

Summary
Given a rectilinear polygon and a set of non-overlapping axis-aligned rectangles, select rectangles that exactly tile the polygon's interior without exceeding its boundary.
Level

Hard8 of 10

Topics
Geometry, Intervals, Implementation
Solved
No attempts yet

Problem

On a two-dimensional plane, a shape is defined by n points, and m axis-aligned rectangles are given. The points of the shape are connected in the given order, and the last point is connected back to the first point.

No two different rectangles share any region with positive area. You may choose some of the given rectangles to cover the shape. A chosen rectangle must not extend outside the shape, and every part of the shape's interior must be covered by a chosen rectangle.

Input

The first line contains two natural numbers n and m (1 <= n <= 1,000, 1 <= m <= 10,000).

Each of the next n lines contains the coordinates of one point of the shape, in order.

Each of the next m lines contains four integers: the x- and y-coordinates of two opposite corners of one rectangle.

Output

Print the number C of selected rectangles on the first line. Then print the numbers of the selected rectangles, one per line, in increasing order.

If the shape cannot be covered, print C = 0.

Examples1

  1. Example 1

    Input
    4 3
0 0
0 2
2 2
2 0
1 0 0 2
1 0 2 2
10 9 9 10
    Expected output
    2
1
2