Array Query Operations

You are given an integer array of size (n) and (q) queries. Each query is in the form ((t, l, r)) where (t) indicates the type of operation to perform on the subarray (a[l \ldots r]). The operations are defined as follows:

• (t = 1): Compute the sum of the subarray, i.e., (\sum_{i=l}^{r} a_i).
• (t = 2): Compute the product of the subarray, i.e., (\prod_{i=l}^{r} a_i).
• (t = 3): Find the maximum element in the subarray, i.e., (\max{a_l, a_{l+1}, \dots, a_r}).

Note that the array uses 1-based indexing. For each query, output the result on a new line.

inputFormat

The first line contains two integers (n) and (q), denoting the size of the array and the number of queries respectively. The second line contains (n) space-separated integers representing the array elements. Each of the next (q) lines contains three space-separated integers (t), (l), and (r) representing a query.

outputFormat

For each query, output a single line containing the result of the operation on the corresponding subarray.## sample

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

6
24
5