题目描述

一行中有 $N$ 个单元格，编号从 $1$ 到 $N$ 。 对于每个 $1 \leq i \lt N$ ，单元格 $i$ 和 $i+1$ 是相邻的。一开始单元格 $i$ 使用颜色 $i$ 绘制。

有 $Q$ 个查询，每个查询都属于以下两种类型之一。

• 1 x c：将与x相邻且颜色相同的单元格绘制为颜色c。

• 2 C：打印颜色 $c$ 的单元格数。

输入格式

第一行两个整数，n和Q。 接下来Q行，包含Q个查询。

输出格式

对于每个查询2，输出对应结果。

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

3
4

数据规模与约定

$1 \leq N \leq 5 \times 10^5$

$1 \leq Q \leq 2 \times 10^5$

在第一种类型的查询中， $1 \leq x \leq N$ 。

在第一和第二类型的查询中， $1 \leq c \leq N$ 。

至少有一个第二类型的查询。所有输入值均为整数。

提示

样例1颜色变化