#5057. 区间k小值5

内存限制:512 MiB 时间限制:20 Sec

题目描述

有n(n<=30000)个位置,q(q<=30000)个操作,操作有两种。一. 1 l r a b 表示在第l个位置到第r个位置,每个位
置加入a到b之间的所有数,一开始所有位置为空。(1<=l<=r<=n,1<=a<=b<=n)二. 2 l r k 表示询问从第l个位置到
第r个位置,第k小的数是多少。(1<=l<=r<=n,1<=k<=n*n*q,保证k合法)

输入格式

第一行两个数n和q。
接下来q行,每行为1 l r a b或2 l r k。
保证第一次操作为操作一。
测试数据均为随机产生。

输出格式

输出每个询问的结果

样例

样例输入


			
2 14
1 1 2 1 2
2 1 2 1
2 1 2 2
2 1 2 3
2 1 2 4
1 2 2 2 2
2 1 2 1
2 1 2 2
2 1 2 3
2 1 2 4
2 1 2 5
2 2 2 1
2 2 2 2
2 2 2 3

样例输出


			
1
1
2
2
1
1
2
2
2
1
2
2

数据范围与提示