#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen("traverse.in","r",stdin);
//	freopen("traverse.out","w",stdout);
CECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECE
//	The T1 is simple but its hardly to write code,i did it for 50min.
//	The T2 is a good DP problem and not very hard,i did it for 60min.
//	But T3 is a S* problem,I think the parson who make this problem is cute.
//	(tips:S* is a suan fa,like A*)
//	I can't write a baoli code for T3.
//	Then I opened T4,its seemed like a data jiegou problem.
//	The 32pts is easy,I write a segtree to do that.
//  But the 100pts is very hard,and I'm too vegetable :(
//  I tried to think the xingzhi A,I should answer the problem:
//  Give you l,r,k,answer the minval-max,k-len qujian's minval(?).
//  I think and think but can't do that.
//  My OI is vegetable,My English is vegetable too! :(

//  Like my CSP-S,my NOIp is bad.
//  In the two matches,I finished T1 and T2 quickly.But I can't do T3 or T4.
//  Why I'm vegetable like this???
//  I'm not a beginner now,I learned OI 400+ days.
//  I'm not Young now,I'm chu er.
//  How I get Qianger?

//  The Bigger dalao in my school is Exp10re,let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

//  The Bigger dalao in my school grade 10 is lilong,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

//  The Bigger dalao in my school grade 9 is cgj0128,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

//  The Bigger dalao in my school grade 8 is _Accepted_100,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

//  The Most vegetable Oier in my school garde 8 is ME,Let's Laugh him!!!!
//lol lol lol lol lol lol lol lol lol lol lol lol lol lol lol lol

//  The Better data jiegou is segtree,because it's Exp10re's belief,Let's Learn it!!!!
//learn learn learn learn learn learn learn learn learn learn

// Wish everyone RP++!!!!
	return 0;
}
