T3 彩色棋盘 (colorful,1s,512MB)

题目描述

有一个 $n$ 行 $n$ 列的网格。

有 $m$ 次操作，每次操作给定 $lx,rx,ly,ry,c$，表示对于所有第 $x$ 行，第 $y$ 列的格点，如果满足 $lx \le x \le rx,ly \le y \le ry$ ，则在这个位置上放入一枚染色为 $c$ 的棋子（同一个格子可以放入多枚棋子）

小 Z 想知道 $m$ 次操作后，有多少个格子内部有全部 $C$ 种颜色的棋子。

输入格式

第一行三个整数 $n,m,C$ 表示棋盘大小，操作次数，颜色种类数。

接下来 $m$ 行，每行五个整数 $lx,rx,ly,ry,c$ 表示一次操作 （ $1 \le c \le C$ ）。

输出格式

输出一行一个整数，表示内部有全部 $C$ 种颜色的棋子的格点数量。

输入输出样例 #1

输入 #1

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

输出 #1

4

说明/提示

对于 $20\%$ 的数据， $n,m \le 500$ 。

对于另外 $20\%$ 的数据，$n \le 2000,m \le 10^5$ 。

对于另外 $20\%$ 的数据，$C=1$ 。

对于另外 $20\%$ 的数据，$C=2$ 。

对于另外 $10\%$ 的数据，$C=3$ 。

对于全部数据，$1 \le n,m \le 10^5, 1 \le C \le 5,1 \le lx \le rx \le n,1 \le ly \le ry \le n,1 \le c \le C$ 。