区间取min

题目背景

你需要维护一个长度为 $n$ 的序列 $a$。初始时，每个位置的值都是正无穷。

接下来会进行 $m$ 次操作。第 $i$ 次操作会给出一个区间 $[l_i,r_i]$ 和一个正整数 $x_i$，并将区间内的所有数更新为：

$$a_j \leftarrow \min(a_j,x_i) \quad (l_i \le j \le r_i)$$

最后，请输出整个序列。

由于 $m$ 可能非常大，如果直接把所有操作写进输入文件，读入本身就会成为瓶颈。因此，本题不会直接给出 $m$ 行操作，而是给出随机种子，由程序生成全部操作。

输入格式

输入一行四个整数：

$$n\ m\ seed\ C$$

其中 $seed$ 是随机数生成器的初始状态，$C$ 是所有 $x_i$ 的取值上界。

使用如下代码生成数据：

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 2147483647;
const long long MUL = 48271;
long long state;
long long nxt()
{
    state = (state * MUL + 1) % MOD;
    return state;
}
int main()
{
    int n, m, C;
    cin >> n >> m >> state >> C;
    while (m--)
    {
        long long p = nxt();
        long long q = nxt();
        long long v = nxt();

        int l = p % n + 1;
        int r = q % n + 1;
        if (l > r)
            swap(l, r);
        long long x = v % C + 1;
    }
    return 0;
}

然后对区间 $[l,r]$ 执行一次取小操作。

输出格式

输出一行 $n$ 个整数，表示最终的序列。

如果某个位置最终仍然是正无穷，请输出 -1。

样例输入

5 4 7 20

样例输出

1 1 1 1 6

样例解释

由种子生成出的四次操作为：

1. $[1,4]$, $x=1$
2. $[1,5]$, $x=11$
3. $[3,4]$, $x=2$
4. $[4,5]$, $x=6$

所以最终序列为 1 1 1 1 6。

数据范围

对于所有测试点：

• $1 \le n \le 10^5$
• $0 \le m \le n\lfloor\sqrt n\rfloor$
• $0 \le seed < 2147483647$
• $1 \le C \le 10^9$

时间限制建议：2s

内存限制建议：512MB