Jinuk's Farm

Time limit2sMemory limit128 MB

Summary
Given up to 50 axis-aligned square paint operations over an N up to 1000 grid, find the largest square subregion containing no fruit type 0 and at most two distinct fruit types.
Level

Hard8 of 10

Topics
Binary search, Prefix sum, Simulation
Solved
No attempts yet

Problem

Jinuk has an N×N square farm. The farm is divided into 1×1 cells, and each cell contains exactly one kind of fruit. Initially, every cell contains fruit type 0.

Jinuk will sow seeds M times. One operation is described by four integers X, Y, L, and F. It means that every cell in the square region with upper-left corner (X, Y) and side length L is planted with fruit type F. If a cell already contains another fruit, the old fruit is removed and replaced by the new one. The upper-left corner of the farm has coordinate (0, 0).

Before leaving for military service, Jinuk wants to give Junkyu a square-shaped part of the farm. The square that Junkyu takes may contain at most two different fruit types, and it must not contain fruit type 0.

Find the maximum area of a square part of the farm that Junkyu can take.

Input

The first line contains two integers N, the side length of the farm, and M, the number of seed-sowing operations.

Each of the next M lines contains four integers X, Y, L, and F describing one operation.

Output

Print the area of the largest square that Junkyu can take.

Constraints

  • 1 ≤ N ≤ 1,000
  • 1 ≤ M ≤ 50
  • 0 ≤ X, Y ≤ N - 1
  • 1 ≤ L ≤ N
  • X + L ≤ N
  • Y + L ≤ N
  • 0 ≤ F ≤ 7

Examples4

  1. Example 1

    Input
    7 3
0 0 7 7
2 2 4 1
3 5 1 5
    Expected output
    25

  2. Example 2

    Input
    3 1
0 0 3 1
    Expected output
    9

  3. Example 3

    Input
    3 1
1 1 1 7
    Expected output
    1

  4. Example 4

    Input
    7 5
0 0 7 7
2 2 4 1
3 5 1 5
1 1 1 5
5 1 1 5
    Expected output
    16