Conference Queries

A conference is being held in a large auditorium with N rooms, each having a fixed capacity. The rooms are numbered from 1 to N. Participants perform tasks and take breaks by entering one of these rooms, and they always try to maximize their relaxation by choosing a room with the highest capacity available among a specified range.

You are given several queries of two types:

• Type 1: "1 p k" - Update the capacity of room p to k.
• Type 2: "2 d" - Consider rooms 1 through d and report two values:
  • the maximum capacity among these rooms, and
  • the sum of their capacities modulo \(10^9+7\).

You are to process all the queries sequentially. Only queries of type 2 require an output. All input is read from standard input (stdin) and all output is written to standard output (stdout).

Input Format: The first line contains two integers N and Q. The second line contains N integers representing the capacities of the rooms. This is followed by Q lines, each representing a query.

Output Format: For every query of type 2, output a line with two space-separated integers: the maximum capacity among the first d rooms and the sum of the capacities modulo \(10^9+7\).

inputFormat

The input begins with two space-separated integers N and Q where:

• N (1 ≤ N ≤ 10⁵): number of rooms.
• Q (number of queries).

The next line contains N space-separated integers, representing the capacity of each room.

Each of the next Q lines contains a query in one of the following formats:

• 1 p k: update the capacity of room p to k (1 ≤ p ≤ N).
• 2 d: output the maximum capacity and the sum modulo \(10^9+7\) for rooms 1 through d (1 ≤ d ≤ N).

outputFormat

For each query of type 2, output a single line containing two space-separated integers:

• the maximum capacity among rooms 1 to d
• the sum of the capacities of these rooms modulo \(10^9+7\)

## sample

5 3
10 20 30 40 50
2 3
1 2 35
2 4

30 60
40 115

</p>