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$，使用示例如下：

namespace Maker{
	unsigned int x0,seed;
	void init() {scanf("%u%u",&x0,&seed);}
	inline unsigned int getnum(){
		x0=(x0<<3)^x0;
		x0=((x0>>5)+seed)^x0;
		return x0;
	}
}
int n,m,typ;
int main(){
	scanf("%d%d%d",&n,&m,&typ);
	// input n numbers as a[1...n]
	Maker::init();
	for(int i=1; i<=m; ++i){
		int l=Maker::getnum()%n+1,r=Maker::getnum()%n+1;
		unsigned int v=Maker::getnum();
		if(l>r) swap(l,r);
		if(typ==1) l=1;
 		// do something
 	}
	// output n numbers of a[1...n]
}

输出格式

输出到 train.out 中。

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

输入输出样例

5 1 0
1 2 3 4 5
233 666

1 94747 94747 94747 5

5 1 1
1 2 3 4 5
456 789

205550 205550 205550 4 5

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

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

数据范围

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