UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

文章可以被抽象成一个长度为 $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$ 小当且仅当 $\exists 1\le i\le n$ 满足 $a_i\lt b_i$,且 $\forall 1\le j\lt 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$。

子任务编号 $n \leq$ $m \leq$ $L \leq$ 特殊性质 分值
$1$ $50$ $9$ $100$ $15$
$2$ $300$ $300$ $500$ $25$
$3$ $5000$ $5000$ $5000$ $20$
$4$ $2\times 10^5$ $2\times 10^5$ $2\times 10^6$ 所有 $a_i=0$ 且 $x_i>0$ $15$
$5$ $2\times 10^5$ $2\times 10^5$ $2\times 10^6$ $25$

对于 $100\%$ 的数据,$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\texttt{s}$

空间限制:$512\texttt{MB}$