Jinuk's Farm

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.

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.

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

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