Coloring Rectangles

Time limit2sMemory limit128 MB

Summary
Given N rectangles, choose exactly K of them to maximize the total visible union area under a max-index-wins overlap rule, picking the lexicographically smallest tie-break.
Level

Hard9 of 10

Topics
Geometry, Dynamic programming, Combinatorics, Greedy
Solved
No attempts yet

Problem

There are N axis-aligned rectangles on a two-dimensional coordinate plane. The rectangles are numbered from 1 to N. Rectangle i has lower-left corner (x_i,1, y_i,1) and upper-right corner (x_i,2, y_i,2).

Choose exactly K of the N rectangles to color. If a region is covered by one or more rectangles, only the rectangle with the largest number among those covering that region is visible. The colored area is the total visible area belonging to the chosen rectangles. Find a choice that maximizes the colored area.

Input

The first line contains two integers N and K.

Each of the next N lines contains four integers x_i,1, y_i,1, x_i,2, and y_i,2, describing one rectangle.

Output

Print the numbers of the K rectangles to color, in increasing order, separated by spaces. If several choices maximize the colored area, print the lexicographically smallest sequence.

Constraints

  • 1 <= K <= N <= 50
  • -10000 <= x_i,1, y_i,1, x_i,2, y_i,2 <= 10000
  • x_i,1 < x_i,2
  • y_i,1 < y_i,2

Examples3

  1. Example 1

    Input
    3 2
1 1 5 3
3 2 7 4
2 5 9 7
    Expected output
    2 3

  2. Example 2

    Input
    7 4
1 1 5 4
2 2 4 3
4 0 6 2
7 1 9 4
1 5 4 7
6 5 9 7
2 5 8 6
    Expected output
    1 3 4 7

  3. Example 3

    Input
    4 3
-1 -5 1 1
2 2 5 6
-2 3 1 7
2 -4 6 -1
    Expected output
    1 2 3