Overwrite Queries

There is an array $A$ of length $N$. Initially, $A_i=0$ for every $i$.

You are also given a permutation $P$ of $1,2,\cdots,N$ and $Q$ queries. Query $i$ is described by three integers $l_i,r_i,x_i$. When it is executed, $A_j$ is replaced by $x_i$ for every $l_i \le j \le r_i$.

You must execute every one of the $Q$ queries exactly once. You may choose their execution order arbitrarily.

Maximize the number of positions $i$ satisfying $A_i=P_i$ after all queries have been executed.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ Q$ $P_1\ P_2\ \cdots\ P_N$ $l_1\ r_1\ x_1$ $l_2\ r_2\ x_2$ $\vdots$ $l_Q\ r_Q\ x_Q$

For each test case, print one integer: the maximum possible number of positions $i$ satisfying $A_i=P_i$ after all queries have been executed.

• $1 \le T \le 100$.
• $1 \le N \le 5\,000$.
• $1 \le Q \le 5\,000$.
• $P$ is a permutation of $1,2,\cdots,N$.
• $1 \le l_i \le r_i \le N$ ($1 \le i \le Q$).
• $1 \le x_i \le N$ ($1 \le i \le Q$).
• The sum of $N$ over all test cases does not exceed $100\,000$.
• The sum of $Q^2$ over all test cases does not exceed $25\,000\,000$.