Problem Statement
Suppose you're given an array of size (). This array contains integers , where the elements satisfy for each . For each , its initial value is .
You need to answer queries in total, where . There are two types of queries:
-
query l r
: Output the value of , where is the product of every element in the subarray to . For this type of query, we have . -
update idx val
: Update the value of toval
. For this type of query, the parameters satisfy and .
Input Specification
The first line contains the integers and , separated by a space.
On each of the next lines are one query each, following the format above.
Output Specification
For each query with type query
, print the result on its own line.
Sample 1
Input:
5 6
update 1 14
update 2 9
query 1 5
update 4 11
query 2 4
Output:
6
9
Query | Array | Output |
---|---|---|
update 1 14 |
[14, 1, 1, 1, 1] |
|
update 2 9 |
[14, 9, 1, 1, 1] |
|
query 1 5 |
[14, 9, 1, 1, 1] |
The output should be |
update 4 11 |
[14, 9, 1, 11, 1] |
|
query 2 4 |
[14, 9, 1, 11, 1] |
The output should be |
Sample 2
Input:
6 7
update 1 5
update 2 2
update 3 3
update 4 4
query 2 4
query 3 5
query 1 5
Output:
4
2
0
We can, again, trace the values in the array:
Query | Array | Output |
---|---|---|
update 1 5 |
[5, 1, 1, 1, 1, 1] |
|
update 2 2 |
[5, 2, 1, 1, 1, 1] |
|
update 3 3 |
[5, 2, 3, 1, 1, 1] |
|
update 4 4 |
[5, 2, 3, 4, 1, 1] |
|
query 2 4 |
[5, 2, 3, 4, 1, 1] |
|
query 3 5 |
[5, 2, 3, 4, 1, 1] |
|
query 1 5 |
[5, 2, 3, 4, 1, 1] |