「CZOI-R1」卡牌
题目背景
Alice 和 Bob 正在玩卡牌游戏。
题目描述
每张卡牌有四个属性:攻击、防御、速度、血量。
我们称一张卡牌能胜过另一张卡牌,当且仅当其至少有三个属性都大于另一张卡牌。
Bob 拥有 $m$ 张卡牌,而 Alice 拥有每个属性值在 $[1, n]$ 的所有 $n^4$ 张卡牌。
现在 Alice 想知道:她有多少张卡牌可以胜过所有 Bob 的卡牌?
输入输出格式
输入格式
第一行包含两个整数 $n, m$,分别表示属性值上限和 Bob 的卡牌数量。
接下来 $m$ 行,每行四个整数 $a_i, b_i, c_i, d_i$,表示 Bob 一张卡牌的属性。
输出格式
输出一行一个整数,表示答案对 $2^{32}$ 取模后的结果。
输入输出样例
输入样例 #1
5 5
2 2 1 2
3 4 2 4
4 3 2 2
1 4 2 3
1 2 4 4
输出样例 #1
32
输入样例 #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
输出样例 #2
243
说明
**【数据范围】**
**本题采用捆绑测试**。
- 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}$):无特殊限制。
对于所有测试数据,$1 \le n, m \le 5 \times 10^5$,$1 \le a_i, b_i, c_i, d_i \le n$。