CF1044A.The Tower is Going Home

On a chessboard with a width of $10^9$ and a height of $10^9$, the rows are numbered from bottom to top from $1$ to $10^9$, and the columns are numbered from left to right from $1$ to $10^9$. Therefore, for each cell of the chessboard you can assign the coordinates $(x,y)$, where $x$ is the column number and $y$ is the row number.

Every day there are fights between black and white pieces on this board. Today, the black ones won, but at what price? Only the rook survived, and it was driven into the lower left corner — a cell with coordinates $(1,1)$. But it is still happy, because the victory has been won and it's time to celebrate it! In order to do this, the rook needs to go home, namely — on the upper side of the field (that is, in any cell that is in the row with number $10^9$).

Everything would have been fine, but the treacherous white figures put spells on some places of the field before the end of the game. There are two types of spells:

• Vertical. Each of these is defined by one number $x$. Such spells create an infinite blocking line between the columns $x$ and $x+1$.
• Horizontal. Each of these is defined by three numbers $x_1$, $x_2$, $y$. Such spells create a blocking segment that passes through the top side of the cells, which are in the row $y$ and in columns from $x_1$ to $x_2$ inclusive. The peculiarity of these spells is that it is impossible for a certain pair of such spells to have a common point. Note that horizontal spells can have common points with vertical spells.

An example of a chessboard.

Let's recall that the rook is a chess piece that in one move can move to any point that is in the same row or column with its initial position. In our task, the rook can move from the cell $(r_0,c_0)$ into the cell $(r_1,c_1)$ only under the condition that $r_1 = r_0$ or $c_1 = c_0$ and there is no blocking lines or blocking segments between these cells (For better understanding, look at the samples).

Fortunately, the rook can remove spells, but for this it has to put tremendous efforts, therefore, it wants to remove the minimum possible number of spells in such way, that after this it can return home. Find this number!

在一个宽度和高度均为 $10^9$ 的棋盘上，行从下到上编号为 $1$ 到 $10^9$，列从左到右编号为 $1$ 到 $10^9$。因此，棋盘上的每个格子均可赋予坐标 $(x,y)$，其中 $x$ 为列号，$y$ 为行号。

每天，黑方与白方棋子都在该棋盘上展开战斗。今天，黑方获胜了，但代价是什么呢？仅剩一枚车（rook）幸存，并被驱赶至左下角——坐标为 $(1,1)$ 的格子。但它依然欣喜，因为胜利已然取得，是时候庆祝了！为此，这枚车需要“回家”，即抵达棋盘的上边界（亦即任意位于第 $10^9$ 行的格子）。

一切本该顺利，但狡诈的白方棋子在对局结束前于棋盘若干位置施加了咒语。咒语分为两类：

• 竖直咒语：每条由一个整数 $x$ 定义，它在第 $x$ 列与第 $x+1$ 列之间生成一条无限长的阻挡线；
• 水平咒语：每条由三个整数 $x_1$、$x_2$、$y$ 定义，它在第 $y$ 行、第 $x_1$ 列至第 $x_2$ 列（含端点）的所有格子的上边沿生成一段阻挡线段。这类咒语的特殊之处在于：任意两条水平咒语之间不可能存在公共点。注意：水平咒语可与竖直咒语存在公共点。

棋盘示例。

回顾一下：车是一种国际象棋棋子，每次移动可到达与其初始位置处于同一行或同一列的任意格子。在本题中，车可以从格子 $(r_0,c_0)$ 移动到格子 $(r_1,c_1)$，当且仅当满足 $r_1 = r_0$ 或 $c_1 = c_0$，且这两格之间不存在任何阻挡线或阻挡线段。（为更好理解，请参阅样例。）

幸运的是，车可以解除咒语，但此举需耗费巨大精力，因此它希望解除尽可能少的咒语，使得解除后能成功返回家中。请找出这个最小数目！

The first line contains two integers $n$ and $m$ ($0 \le n,m \le 10^5$) — the number of vertical and horizontal spells.

Each of the following $n$ lines contains one integer $x$ ($1 \le x \lt 10^9$) — the description of the vertical spell. It will create a blocking line between the columns of $x$ and $x+1$.

Each of the following $m$ lines contains three integers $x_1$, $x_2$ and $y$ ($1 \le x_{1} \le x_{2} \le 10^9$, $1 \le y \lt 10^9$) — the numbers that describe the horizontal spell. It will create a blocking segment that passes through the top sides of the cells that are in the row with the number $y$, in columns from $x_1$ to $x_2$ inclusive.

It is guaranteed that all spells are different, as well as the fact that for each pair of horizontal spells it is true that the segments that describe them do not have common points.

第一行包含两个整数 $n$ 和 $m$（$0 \le n,m \le 10^5$）—— 分别表示垂直法术和水平法术的数量。

接下来的 $n$ 行中，每行包含一个整数 $x$（$1 \le x \lt 10^9$）—— 描述一个垂直法术。该法术将在第 $x$ 列与第 $x+1$ 列之间创建一条阻挡线。

再接下来的 $m$ 行中，每行包含三个整数 $x_1$、$x_2$ 和 $y$（$1 \le x_{1} \le x_{2} \le 10^9$，$1 \le y \lt 10^9$）—— 描述一个水平法术。该法术将创建一条阻挡线段，该线段经过第 $y$ 行中所有列号从 $x_1$ 到 $x_2$（含端点）的单元格的上边界。

保证所有法术互不相同；此外，对任意两个水平法术，描述它们的线段之间没有公共点。

In a single line print one integer — the minimum number of spells the rook needs to remove so it can get from the cell $(1,1)$ to at least one cell in the row with the number $10^9$

在一行中输出一个整数——车需要移除的法术的最少数量，使得它能够从单元格 $(1,1)$ 到达第 $10^9$ 行中的至少一个单元格。

In the first sample, in order for the rook return home, it is enough to remove the second horizontal spell.

Illustration for the first sample. On the left it shows how the field looked at the beginning. On the right it shows how the field looked after the deletion of the second horizontal spell. It also shows the path, on which the rook would be going home.

In the second sample, in order for the rook to return home, it is enough to remove the only vertical spell. If we tried to remove just one of the horizontal spells, it would not allow the rook to get home, because it would be blocked from above by one of the remaining horizontal spells (either first one or second one), and to the right it would be blocked by a vertical spell.

Illustration for the second sample. On the left it shows how the field looked at the beginning. On the right it shows how it looked after the deletion of the vertical spell. It also shows the path, on which the rook would be going home.

In the third sample, we have two horizontal spells that go through the whole field. These spells can not be bypassed, so we need to remove both of them.

Illustration for the third sample. On the left it shows how the field looked at the beginning. On the right it shows how the field looked after the deletion of the horizontal spells. It also shows the path, on which the rook would be going home.

In the fourth sample, we have no spells, which means that we do not need to remove anything.

In the fifth example, we can remove the first vertical and third horizontal spells.

Illustration for the fifth sample. On the left it shows how the field looked at the beginning. On the right it shows how it looked after the deletions. It also shows the path, on which the rook would be going home.

在第一个样例中，为了使车能够返回家中，只需移除第二条水平法术即可。

第一个样例示意图。左侧显示棋盘初始状态；右侧显示移除第二条水平法术后的棋盘状态，并同时标出了车将沿其返回家中的路径。

在第二个样例中，为了使车能够返回家中，只需移除唯一的一条竖直法术即可。若仅尝试移除其中一条水平法术，则无法使车回家，因为车将被上方剩余的某一条水平法术（第一条或第二条）阻挡，且在右方还会被一条竖直法术阻挡。

第二个样例示意图。左侧显示棋盘初始状态；右侧显示移除竖直法术后的棋盘状态，并同时标出了车将沿其返回家中的路径。

在第三个样例中，存在两条横贯整个棋盘的水平法术。这些法术无法绕过，因此必须将它们全部移除。

第三个样例示意图。左侧显示棋盘初始状态；右侧显示移除水平法术后棋盘的状态，并同时标出了车将沿其返回家中的路径。

在第四个样例中，不存在任何法术，这意味着无需移除任何东西。

在第五个样例中，我们可以移除第一条竖直法术和第三条水平法术。

第五个样例示意图。左侧显示棋盘初始状态；右侧显示执行移除操作后的棋盘状态，并同时标出了车将沿其返回家中的路径。