调整队形

Time Limit: 2000MS

Memory Limit: 65535Kb

Description

YQ很喜欢跟小孩子玩,因为她觉得他们很可爱。正在实习的她就面对一群小朋友。现在她要给这些小朋友排一下队,考虑到很多因素,她要对刚开始排好的队伍进行下面的调整。

1 Move a b k: 把排在a到b的小朋友一起移动到排在k的小朋友后面。如果当前的队伍是1 2 3 4 5 6 7 8,进行move 3 5 4 ,首先把[3,5]的数取出,剩下的数为1 2 6 7 8,再把这些小朋友插到排在第4的小朋友后面,最后的队伍为 1 2 6 7 3 4 5 8。如果k=0,表示把这些小朋友放到队首。

2 Flip a b :把排a到b的小朋友的,顺序颠倒一下。如果当前的队伍为1 2 5 4 3 6 7 8,进行flip 3 5, 最后的队尾为1 2 3 4 5 6 7 8。

 为了让这些小孩子能听自己的话,刚开始的时候,YQ给每个小朋友都发了一下糖果。她现在请你帮为她做完成两件事。

1 她在调整队伍的过程,她想知道某个区间的小朋友手中拿到的糖果最多是多少个。当输入为Max a b 时,输出排在a到b的小朋友拿到最多的糖果是多少。

2 最后在所有的输入结束,输出现在队伍中每个小朋友手中的糖果的个数。

Input

输入数据第一行两个整数N和M,表示小朋友的个数。第二行有N个数,表示刚开始每个小朋友手中拿到的糖果个数。接下来有M行。输入格式为题目描述中得Move,Flip和Max 三种。其中,1<N,M<=100,000,小朋友手中的糖果个数x,满足0<x<100,000。所有的输入数据都是合法的。

Output

对于每个max询问,输出当前区间最多的糖果个数。

最后再输出经过调整后队伍中每个小朋友手中的糖果的个数。

Sample Input

6 4
3 2 1 6 5 4
Max 1 3
Move 4 6 0
Max 1 3
Flip 1 6

Sample Output

3
6	
1 2 3 4 5 6

Hint

刚开始每个小朋友手中的糖果为 3 2 1 6 5 4 所以询问排在第1到第3的小朋友手中最多糖果个数为3。

Move操作之后的每个小朋友手中糖果为 6 5 4 3 2 1。此时再询问排在第1到第3的小朋友手中最多糖果个数,为6。

Flip 1 6操作结束后,最后的队伍中每个小朋友的糖果为 1 2 3 4 5 6。

Source

张俊杰

提交代码