Background

Alice and Bob are playing a card game.

Problem Description

Each card has four attributes: attack, defense, speed, and health.

We say a card can defeat another card if and only if it is greater than the other card in at least three attributes.

Bob has $m$ cards, and Alice has all $n^4$ cards whose each attribute value is in $[1, n]$.

Now Alice wants to know: how many cards does she have that can defeat all of Bob's cards?

Input Format

The first line contains two integers $n, m$, representing the upper bound of attribute values and the number of Bob's cards.

The next $m$ lines each contain four integers $a_i, b_i, c_i, d_i$, representing the attributes of one of Bob's cards.

Output Format

Output one line with one integer, representing the result modulo $2^{32}$.

5 5
2 2 1 2
3 4 2 4
4 3 2 2
1 4 2 3
1 2 4 4

32

10 10
7 8 5 2
5 9 9 4
3 8 4 3
5 6 5 1
5 5 2 4
9 5 5 1
3 7 2 5
4 4 5 4
9 6 1 5
3 7 3 7

243

Hint

Constraints

This problem uses bundled testdata.

• Subtask #1 ($10\text{ pts}$): $n, m \le 50$.
• Subtask #2 ($10\text{ pts}$): $n, m \le 5 \times 10^3$.
• Subtask #3 ($20\text{ pts}$): $d_i = 1$.
• Subtask #4 ($20\text{ pts}$): $n, m \le 10^5$.
• Subtask #5 ($40\text{ pts}$): No special constraints.

For all testdata, $1 \le n, m \le 5 \times 10^5$, and $1 \le a_i, b_i, c_i, d_i \le n$.

Translated by ChatGPT 5