덮어쓰기와 쿼리

길이 $N$의 배열 $A$가 있다. 처음에는 모든 $A_i$가 $0$이다.

또한 $1,2,\cdots,N$의 순열 $P$와 $Q$개의 쿼리가 주어진다. $i$번 쿼리는 세 정수 $l_i,r_i,x_i$로 주어지며, 실행하면 모든 $l_i \le j \le r_i$에 대해 $A_j$를 $x_i$로 바꾼다.

$Q$개의 쿼리를 각각 정확히 한 번씩 실행해야 한다. 실행 순서는 자유롭게 정할 수 있다.

모든 쿼리를 실행한 뒤 $A_i=P_i$를 만족하는 위치 $i$의 개수를 최대화하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$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$

각 테스트 케이스마다, 모든 쿼리를 실행한 뒤 $A_i=P_i$인 위치의 개수로 가능한 최댓값을 한 줄에 출력한다.

• $1 \le T \le 100$.
• $1 \le N \le 5\,000$.
• $1 \le Q \le 5\,000$.
• $P$는 $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$).
• 모든 테스트 케이스에 대한 $N$의 합은 $100\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q^2$의 합은 $25\,000\,000$ 이하이다.