Circular Swap

View as PDF

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 512M

Problem type

Given a circular sequence with integers, denoted as in clockwise order. Bob is going to perform operations. Each operation will give an interval and an integer . Bob will modify the sequence as follows.

for (int i = L; i <= R; i++) {
if (a[i] > x) swap(a[i], x);
}

Since the sequence is circular, the given may be less than . Bob will perform the above operation from to in clockwise order. After each operation, Bob wants to know the value of . Can you write a program to help him?

Input Specification

The first line of input contains two integers and (, ), indicating the length of the sequence and the number of operations.

Each of the following lines contains one integer (), the -th element in the sequence.

Each of the following lines contains three integers , , and (, ), indicating an operation.

Output Specification

Output lines. Each line contains one integer, the final value of after the operation.

, .
, .

Sample Input 1

6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3

Sample Output 1

7
9
8
7
8
6
5

Explanation

• The initial sequence is like .
• After the st operation, it's like and .
• After the nd operation, it's like and .
• After the rd operation, it's like and .

Sample Input 2

4 2
5
2
4
7
1 4 3
1 4 1

Sample Output 2

7
5