集体会议

时间限制：2 s

空间限制：256 MiB

题目描述

现有 $n$ 人构成的集体，一开始第 $i$ 人持有的观点为 $a_i$。

接下来有 $q$ 个事件发生，每个事件是以下两种之一：

• 集体会议事件：给定 $l,r$，第 $l,l+1,\cdots,r$ 人进行集体会议，设 $x$ 是 $a_l,a_{l+1},\cdots,a_r$ 的众数（若有多个数出现次数一致，取最早出现的数，例如 $a_3,a_4,\cdots,a_7=\{1, 3, 4, 4, 3\}$，则 $a_3,a_4,\cdots,a_7$ 的众数为 $3$），即 $x$ 是这些人中的主流观点，持有该观点的人数最多。会议后，参与会议的所有人的观点更改为 $x$。
• 观点改变事件：给定 $idx,x$，第 $idx$ 人经过思考后，改变其观点为 $x$。

在 $q$ 个事件完全发生后，请给出每个人持有的观点。

输入格式

第一行两个整数 $n,q$，表示集体的人数和事件的数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots a_n$，表示一开始每个人的观点。

接下来 $q$ 行每行 $3$ 个整数。其中第一个整数为事件种类 $op$，然后：

• 若 $op=1$，接下来跟着两个整数 $l,r$，表示一次集体会议事件。
• 若 $op=2$，接下来跟着两个整数 $idx,x$，表示一次观点改变事件。

输出格式

一行 $n$ 个整数，表示所有事件完全发生后，每个人持有的观点。

样例输入1

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

样例输出1

1 1 2 1 2

样例1解释

第一次事件后：[1 3 2 2 2]

第二次事件后：[1 1 2 2 2]

第三次事件后：[1 1 1 1 2]

第四次事件后：[1 1 2 1 2]

数据范围与约定

对于 $50\%$ 的数据，$1\le n,q\le 3000$

对于 $100\%$ 的数据，$1\le n,q\le 5\times 10^5, 1\le l\le r \le n,1\le idx,x,a_i\le n$