徐老师的广场舞

文件读写

• 输入文件dance.in
• 输出文件dance.out

限制

• 1000ms
• 512MB

题目描述

徐老师家楼下最近经常有阿姨们来跳广场舞，但是广场舞的音乐实在是太吵了，于是徐老师开始观察阿姨们的行动规律

他发现可以把他们所住的街道看作一条直线，一共被划分成 $n$ 个区域，编号分别为 $1 \sim n$

而每次阿姨们来跳广场舞时，她们会占领连续的一段区域 $[l,r]$，并且在其中每个区域内各放置一个音箱，并将所有音箱的音量设置为 $p$，这样就可以让所有阿姨同步听到音乐，跟上节奏。

而徐老师观察后发现，音箱的外放音量会随着距离衰减，每间隔一个区域，音量就会降低 $1$

形式化的来说，对于一个放置在区域 $x$，音量大小为 $p$ 的音箱：

在 $x$ 区域能听到的音量为 $p$

在 $x-1$ 和 $x+1$ 区域能听到的音量为 $p-1$

在 $x-2$ 和 $x+2$ 区域能听到的音量为 $p-2$

在 $x-3$ 和 $x+3$ 区域能听到的音量为 $p-3$

...

在 $x-p+1$ 和 $x+p-1$ 区域能听到的音量为 $1$

在 $x-p$ 和 $x+p$ 区域不会听到这个音箱发出的声音

由于同一群阿姨带来的所有音箱会进行蓝牙连接，同步播放声音，所以我们可以认为一个区域 $y$ 如果受到这群阿姨带来的多个音箱的影响，只考虑能听到最大音量的那个音箱

例如在 $y$ 区域能听到两个音箱发出的声音，一个为 $5$，一个为 $8$，那么我们认为在 $y$ 区域能听到的音量即为 $8$

在一天里，来了许许多多群阿姨，又走了许许多多群阿姨

现在徐老师想知道，在某个连续区域 $i \sim j$ 内的住户中，至今为止听到过的最大的音箱音量是多少？

P.S.1 不会有两群阿姨同时来跳广场舞，一定是一群阿姨离开后才会来下一群阿姨

输入格式

输入第一行包含两个整数 $n,T$，表示一个有 $n$ 个区域，发生了 $T$ 个事件（这里的事件指有一群阿姨来跳广场舞，或者徐老师的询问）

接下来 $T$ 行，每行包含一次事件的描述：

• 1 l r p 表示现在来了一群阿姨，占领了区域 $[l,r]$ 跳广场舞，并且他们的音箱音量为 $p$
• 2 i j 表示徐老师想询问，到现在为止，编号 $i \sim j$ 的区域内住户听到过的最大的音箱音量是多少

输出格式

对于徐老师的每次询问，输出结果

数据范围

对于所有数据保证：$1 \leq n, T \leq 500000, 0 \leq p \leq 10^9$

其中部分数据满足以下特殊性质：

样例输入

10 7
1 3 5 3
2 4 4
2 6 10
1 5 7 4
2 1 1
2 2 3
2 1 10

样例输出

3
2
1
3
4

样例解释

对于第一群阿姨，她们占领了 $3 \sim 5$ 这三个区间，每个区间放置了一个音量为 $3$ 的音箱，那么整个街道所有区域能听到的音箱音量为 $[1,2,3,3,3,2,1,0,0,0]$ 对于第一次询问，$4$ 区域的住户听到过的最大的音箱音量为 $3$ 对于第二次询问，$6$ 区域的住户听到过的最大的音箱音量为 $2$，7区域的住户听到的音箱音量为 $1$，所以最大值为 $2$

对于第二群阿姨，她们占领了 $5 \sim 7$ 这三个区间，每个区间放置了一个音量为 $4$ 的音箱，那么整个街道所有区域能听到的音箱音量为 $[0,1,2,3,4,4,4,3,2,1]$ 对于第三个询问，$1$ 区域的住户在上一群阿姨来的时候听到过的音量为 $1$，第二群阿姨来的时候听到过的音量为 $0$，所以他至今为止听到过的最大音量为 $1$ 对于第四个询问，$2$ 区域的住户在两群阿姨来的时候听到过的音量分别为 $2,1$，$3$ 区域的住户在两群阿姨来的时候听到过的音量分别为 $3,2$，所以他们至今为止听到过的最大音量为 $3$ 对于第五个询问，整个街道上所有住户听到过的最大的音量为 $4$