T44252 线索

祭典即将举行，编织结绳的工作正在紧张地开展着。而这天，泷和三叶交换了身体，三叶担心泷不会编结绳，在日记里留下了编织结绳的方法，并请你来帮助泷编好结绳。

将丝线汇集在一起，编织成形；扭曲，缠绕，有时又还原，再连接；那就是结，那就是时间。 结绳是神的思想的重要载体。编织结绳有两个基本操作：染色和交换。染色是为了寄托人民对美好生活的向往，而交换则是要在线与线之间、人与人之间建立联系，形成结，建立羁绊。 现在泷要编织由$n$条丝线组成的结绳。这$n$条结绳紧紧排成一排，按位置把它们叫作第$1,2,\cdots ,n$条丝线。编织开始前，每条丝线有自己的颜色（用一个正整数来表示），第$i(1\le i \le n)$条丝线的颜色为$c_{i}$。 三叶给泷的编织方法有$m$步，第$j(1\le j\le m)$步用$4$个正整数$a_{j}, l_{j}, r_{j}, x_{j}$来描述。 $a_{j}$的值为$1$或$2$。 若$a_{j}=1$，则表示这步操作为染色，这时要把$[l_{j}$,$r_{j}]$这个区间上的丝线全部染成$x_{j}$这种颜色，保证$l_{j}\le r_{j}$。 若$a_{j}=2$，则表示这步操作为交换，这时要把$l_{j}$位置上的丝线和$r_{j}$位置上的丝线交换。作为它们交换的纪念，交换的同时要把这两条丝线染成$x_{j}$这种颜色。注意，$a_{j}=2$时不保证$l_{j}\le r_{j}$，但保证$l_{j} \neq r_{j}$。 两条丝线交换后会形成永久的联系。这种联系体现在，交换发生后，若其中任意一条丝线被染上了某种颜色，另一条丝线也会被同时染上相同的颜色。这种羁绊还具有传递性，即如果$1$与$2$建立了羁绊，$2$又与$3$建立了羁绊，那么我们就认为$1$也与$3$建立了羁绊。注意，丝线不能与自己形成结。 注意，如果交换的两根丝线在交换前已经建立了联系，进行交换操作后它们的联系不会改变，但仍要对它们染色以示纪念。 为了检查编织的效果，泷想知道编织完毕后，每一个位置上丝线的颜色。此外，为了保证结绳的联系足够牢固，泷还需要知道与每条丝线建立联系的丝线的数目。你能帮助他吗？

输入共$(m+2)$行。 第$1$行有$2$个以空格分隔的正整数$n, m$，分别代表丝线的数目和编织步骤的数目。 第$2$行有$n$个以空格分隔的正整数，第$i$个正整数$c_{i}$表示编织开始前第$i$条丝线的颜色。 以下$m$行每行有$4$个以空格分隔的正整数$a_{j},l_{j},r_{j},x_{j}$，描述编织的步骤，意义如上所述。

输出共$2$行。 第$1$行有$n$个以空格分隔的正整数，第$i$个正整数$c'_{i}$代表编织完毕后第$i$个位置上的丝线的颜色。 第$2$行有$n$个以空格分隔的非负整数，第$i$个非负整数$d_{i}$代表编织完毕后与第$i$个位置上的丝线建立联系的丝线数目。

上文中的”建立联系“、”形成结“、”建立羁绊”为同义词。 --------- 对于5%的数据，保证$n,m\le 100$。 对于另外5%的数据，保证$n,m \le 500$。 对于另外10%的数据，保证$n,m \le 1000$。 对于另外20%的数据，保证$n,m \le 5000$。 对于剩余60%的数据，保证$n,m \le 100000$。  对于100%的数据，保证$c_{i},x_{j}\le 10^{9}, a_{j}\in \{1,2\},1\le l_{j},r_{j} \le n$。 --------