小青鱼计划越过高高的龙门，成为大青龙。但是仅凭小青鱼的力量是越不过龙门的。所以它参加了龙王阁新年文会，如果在群鱼中夺魁，就能获得神奇的文江学海之冠。

文章可以被抽象成一个长度为 $n$ 的数列 $x_1,x_2,\cdots ,x_n$，群鱼认为，数列的字典序越大，文章的文采越高。

小青鱼已经写好了文章的草稿，是一个数列 $a_1,a_2,\cdots ,a_n$。在深思熟虑后，它拟定了 $m$ 条可能的修改，第 $i$ 条修改可以用一对 $(l_i,r_i)$ 和 $r_i-l_i+1$ 个整数 $x_1,x_2,\cdots ,x_{r_i-l_i+1}$ 来描述，如果执行这个修改，会同时对所有 $l_i\le j\le r_i$，将 $a_j$ 的值改为 $x_{j-l_i+1}$。

现在小青鱼想从这 $m$ 个修改计划中选择一个子集并按照任意顺序执行它们。设最终文章是数列 $b_1,b_2,\cdots ,b_n$ ，它希望 $b_1,b_2,\cdots ,b_n$ 的字典序尽可能大。求最终 $b_1,b_2,\cdots ,b_n$ 分别是多少。

注： 对于两个长度为 $n$ 的序列 $a,b$，称 $a$ 的字典序比 $b$ 小当且仅当 $\mathrm{\exists }1\le i\le n$ 满足 $a_i<b_i$，且 $\mathrm{\forall }1\le j<i$ 都有 $a_j=b_j$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\cdots ,a_n$。

接下来 $m$ 行先是两个整数 $l_i,r_i$，接下来 $r_i-l_i+1$ 个整数 $x_1,x_2,\cdots ,x_{r_i-l_i+1}$。

输出格式

输出一行 $n$ 个整数 $b_1,b_2,\cdots ,b_n$，表示字典序最大的 $b$，相邻整数之间用一个空格隔开。

样例一

input

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

output

3 2 1 3 2

explanation

• 先执行修改 $1$，将文章改为 $(1,1,1,3,2)$。
• 再执行修改 $2$，将文章改为 $(3,2,1,3,2)$。

样例二、三

见下发文件。

数据范围

记 $L=\sum r_i-l_i+1$。

对于 $100\mathrm{\%}$ 的数据，$1\le n,m\le 2\times {10}^5,1\le L\le 2\times {10}^6,0\le a_i,x_i\le {10}^9$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$