maximum-power

In the Pradnya Planet, there are n aliens which have different powers.
The aliens are numbered from A1 to An, and their respective powers are denoted
from P1 to Pn. Now, these aliens have to fight against another planet for d days.
For each day, either of these 2 situations can occur:
1. If situation is 'C' 
Any two aliens from range Al to Ar will have to fight against another planet
(The resultant power of the 2 aliens fighting will be the product of their individual powers)

2. If situation is 'P' 
An alien Ai changes its power to p

Now, Yash Lahoti being the "Big Boss" of these n aliens, needs to make sure that the 
2 aliens going on any day produce the maximum power. Help Rushabh determine the maximum
power which can be produced each day.
Input Format:
First line contains two space separated integers n and d, denoting the number of aliens and number of days.
Each of the next n lines contains the power of the n respective aliens

Each of the next d lines can contain 3 space separated inputs of two types:
Type 1: 'C'       l           r
    where 'C' represents the situation, 
l and r represents the range of aliens Al to Ar, out of which any two can go to fight.

Type 2: 'P'          i            p
    where 'P' represents the situaton, 
i and p represent that the power of alien Ai becomes p
Output Format:
For each of the situation of type 'P', output a single line one integer deonting the maximum power which 
can be produced by any of the 2 aliens from range (Al to Ar).
Constraints:
2 ≤ n ≤ 10^5
-4*10^4 ≤ P1, P2 ,...Pn ≤ 4*10^4
1 ≤ d ≤ 10^6
1 ≤ l < r ≤n
1 ≤ i ≤ n
-4*10^4 ≤ p ≤ 4*10^4

SAMPLE INPUT
5 3
-4 1 3 4 -2
C 1 3
P 4 -4
C 1 4

SAMPLE OUTPUT
3
16

Explanation

For the first day, aliens with powers 1 and 3(A2 and A3) will give maximum power = 3

For the second day, the power of A4 will change to -4
Thus the powers of aliens will now be: -4, 1, 3, -4, -2

For the third day, 1st and 4th alien(A1 and A4) with powers -4 and -4 will give maximum power=16

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: