题目描述

给定一个长度为 $n$ 的序列 $a$，$a_i$ 为第 $i$ 个点的颜色。现给出一些区间修改操作，需要求出在开始和每次操作后，序列中共有多少种不同的颜色。

输入格式

第一行两个整数 $n$，$q$，表示序列长度和操作数

接下来 $q$ 行，每行三个整数 $x$，$y$，$z$，表示将区间 $[l,r]$ 的颜色修改为 $z$

输出格式

共 $q+1$ 行，每行一个整数，表示开始和每次操作后的答案

样例 #1

样例输入 #1

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

样例输出 #1

3
2
3

提示

对于20%的数据：$1\leq n,q\leq 5\times{10}^3$

对于50%的数据：$1\leq n,q\leq 1\times{10}^5$

对于100%的数据：

$1\leq n,q\leq 5\times{10}^5$

$1\leq a_i,z\leq 5\times{10}^5$

$1\leq x\leq y\leq n$