Algorithms and Data Structures

Range Min-Max Query

You are given an array of n elements and q queries. There are two types of queries:
  1. Get the minimum and the maximum within the given range
  1. Update the array at a given location.
Your task is to process the queries efficiently.

Input

The first line of the input contains two integers n and q (1 ≤ n, q ≤ 100 000), representing the number of elements in the array and the number of queries, respectively.
The second line contains n space-separated integers (), representing the initial elements of the array.
The following q lines each represent a query:
  1. For range minimum and maximum pair queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the minimum and maximum pair needs to be calculated.
  1. For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value.

Output

For each range minimum and maximum pair query, print the minimum and maximum pair of the elements within the given range on separate lines.

Examples

Input
Output
6 4 12 8 16 24 36 48 1 2 5 2 4 10 1 1 6 1 3 6
8 36 8 48 10 48
 

Constraints

Time limit: 0.45 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue