P10800 "CZOI-R1" Cards

Alice and Bob are playing a card game.

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? #

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 one line with one integer, representing the result modulo $2^{32}$.

**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