CF1753F.Minecraft Series

Little Misha goes to the programming club and solves nothing there. It may seem strange, but when you find out that Misha is filming a Minecraft series, everything will fall into place...

Misha is inspired by Manhattan, so he built a city in Minecraft that can be imagined as a table of size $n \times m$. $k$ students live in a city, the $i$-th student lives in the house, located at the intersection of the $x_i$-th row and the $y_i$-th column. Also, each student has a degree of his aggressiveness $w_i$. Since the city turned out to be very large, Misha decided to territorially limit the actions of his series to some square $s$, which sides are parallel to the coordinate axes. The length of the side of the square should be an integer from $1$ to $\min(n, m)$ cells.

According to the plot, the main hero will come to the city and accidentally fall into the square $s$. Possessing a unique degree of aggressiveness $0$, he will be able to show his leadership qualities and assemble a team of calm, moderate and aggressive students.

In order for the assembled team to be versatile and close-knit, degrees of aggressiveness of all students of the team must be pairwise distinct and must form a single segment of consecutive integers. Formally, if there exist students with degrees of aggressiveness $l, l+1, \ldots, -1, 1, \ldots, r-1, r$ inside the square $s$, where $l \le 0 \le r$, the main hero will be able to form a team of $r-l+1$ people (of course, he is included in this team).

Notice, that it is not required to take all students from square $s$ to the team.

Misha thinks that the team should consist of at least $t$ people. That is why he is interested, how many squares are there in the table in which the main hero will be able to form a team of at least $t$ people. Help him to calculate this.

小Misha去编程俱乐部，却什么题都不做。这看起来很奇怪，但当你得知Misha正在制作一个《我的世界》（Minecraft）系列视频时，一切就都明白了……

Misha深受曼哈顿的启发，因此他在《我的世界》中建造了一座城市，该城市可被想象为一个 $n \times m$ 的表格。城中有 $k$ 名学生，第 $i$ 名学生住在位于第 $x_i$ 行、第 $y_i$ 列交叉处的房屋中。此外，每名学生还拥有一个表示其攻击性的数值 $w_i$。由于城市规模非常庞大，Misha决定将他系列视频的情节活动范围限制在某个正方形区域 $s$ 内，该正方形的边与坐标轴平行。正方形边长必须为介于 $1$ 到 $\min(n, m)$（含端点）之间的整数。

根据剧情设定，主角将来到这座城市，并意外落入正方形区域 $s$ 中。主角具有独一无二的攻击性值 $0$，他将借此展现领导才能，并组建一支由性格沉稳、中庸及富有攻击性的学生构成的团队。

为使所组建的团队具备多样性与凝聚力，团队中所有学生的攻击性值必须两两互异，且构成一段连续的整数区间。形式化地说：若在正方形 $s$ 内存在攻击性值分别为 $l, l+1, \ldots, -1, 1, \ldots, r-1, r$ 的学生（其中 $l \le 0 \le r$），则主角便能组建一支共 $r-l+1$ 人的团队（当然，主角本人也包含在该团队中）。

注意：并非必须将正方形 $s$ 内的所有学生都纳入团队。

Misha认为团队人数至少应为 $t$ 人。因此，他关心的是：在整个 $n \times m$ 表格中，有多少个正方形区域 $s$，使得主角能在其中组建一支不少于 $t$ 人的团队？请帮助他计算这一数量。

The first line contains four integers $n$, $m$, $k$ and $t$ ($1 \le n, m \le 40\,000$, $1 \le n \cdot m \le 40\,000$, $1 \le k \le 10^6$, $1 \le t \le k + 1$) — the number of rows and columns in the table, and the number of students living in the city, respectively.

Each of the following $k$ lines contains three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$, $1 \le \lvert w_i \rvert \le 10^9$) — the number of row and column, where the $i$-th student is living, and the degree of his aggressiveness.

第一行包含四个整数 $n$、$m$、$k$ 和 $t$（$1 \le n, m \le 40\,000$，$1 \le n \cdot m \le 40\,000$，$1 \le k \le 10^6$，$1 \le t \le k + 1$），分别表示表格的行数与列数，以及居住在该城市的总学生人数。

接下来的 $k$ 行中，每行包含三个整数 $x_i$、$y_i$ 和 $w_i$（$1 \le x_i \le n$，$1 \le y_i \le m$，$1 \le \lvert w_i \rvert \le 10^9$），表示第 $i$ 位学生所居住的行号与列号，以及其攻击性程度。

Print one integer — the number of ways to choose the square $s$ in such way that the main hero will be able to form a team of at least $t$ people.

输出一个整数——选择方格 $s$ 的方案数，使得主角能够组成至少 $t$ 人的队伍。

1. In the first example the main hero will not be able to form a team of more than one person in any square $s$.

   Illustration for the first example.

2. In the second example there are two ways to select square $s$. Both of them are illustrated below. In one of them the main hero will be able to form a team of students with degrees of aggressiveness $[0, 1]$, and in the another — with degrees of aggressiveness $[0, 1, 2]$. Notice, that the main hero with degree of aggressiveness $0$ will be included to the team regardless of the chosen square.

   Illustration for the second example.

3. In the third example there are four ways to select square $s$. All of them are illustrated below. The main hero will be able to form a team with degrees of aggressiveness: $[-1,0,1]$, $[0,1]$, $[0,1]$, $[-1, 0, 1]$, respectively.

   Illustration for the third example.

4. 在第一个例子中，主角无法在任意正方形 $s$ 内组成人数超过一人的队伍。

第一个例子的示意图。

2. 在第二个例子中，存在两种选择正方形 $s$ 的方式，如下图所示。其中一种方式下，主角能够组建一支学生队伍，其攻击性程度分别为 $[0, 1]$；另一种方式下，其攻击性程度为 $[0, 1, 2]$。注意：无论选择哪一个正方形，攻击性程度为 $0$ 的主角都将被包含在队伍中。

第二个例子的示意图。

3. 在第三个例子中，存在四种选择正方形 $s$ 的方式，如下图所示。主角分别能组建攻击性程度为 $[-1,0,1]$、$[0,1]$、$[0,1]$、$[-1, 0, 1]$ 的队伍。

第三个例子的示意图。