You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

开草莓列车一定要快，落地了草莓就没了。

题目描述

给定一个序列 $\{a_n\}$，有 $m$ 次操作，形如 l r v，表示将 $[l,r]$ 的每个 $a_i$ 变为 $\max(a_i,v)$。

求最终的序列。

输入格式

从 train.in 中读入数据。

为了避免过量的输入，此题使用特殊的读入格式。

第一行三个正整数 $n,m,type$ 表示序列长度、操作次数和数据类型。

当 $type=1$ 时，请手动固定左端点 $l=1$。

第二行包含 $n$ 个数，表示初始的序列。

最后一行输入 $x_0,seed$，使用示例如下：

int n,m,typ,seed;
int main(){
	scanf("%d%d%d%d",&n,&m,&typ,&seed);
	mt19937 rnd(seed);
        // input n numbers as a[1...n]
	for(int i=1; i<=m; ++i){
		int l=rnd()%n+1,r=rnd()%n+1;
		unsigned int v=rnd();
		if(l>r) swap(l,r);
		if(typ==1) l=1;
 		// do something
 	}
	// output n numbers of a[1...n]
}

输出格式

输出到 train.out 中。

一行 $n$ 个整数，表示序列的每个数。

输入输出样例

样例输入 1

5 1 0
1 2 3 4 5
233 666

样例输出 1

1 94747 94747 94747 5

样例输入 2

5 1 1
1 2 3 4 5
456 789

样例输出 2

205550 205550 205550 4 5

样例解释 $1$：第一个操作为 2 4 94747。

样例解释 $2$：第一个操作为 1 3 205550。

数据范围

对于所有数据：$a_i\le 10^5$，有且仅有子任务 $4$ 的 $type=1$。