Problem Background

Alice and Bob are playing a card game.

Problem Description

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

A card is said to defeat another card if and only if it has at least three attributes greater than the other card.

Bob has $m$ cards, while Alice has all $n^4$ cards with each attribute value in the range $[1, n]$.

Now, Alice wants to know how many of her cards can defeat all of Bob's cards.

Input Format

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

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 a single integer, which is the answer modulo $2^{32}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

32

Sample Input #2

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

Sample Output #2

243

Notes

[Data Range]

This problem uses batched testing.

• 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 restrictions.

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

见题面 Input 部分

见题面 Output 部分