|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
You are given an array $A$ with $n$ integers. You are asked to perform $q$ queries on this array. Queries can be of two types:
- q i j: Within the interval $[i, j]$, find the number of distinct multiples of 2 and 3, but not both.
- u p v: Update the value of the array at index $p$ with the value $v$, that is set $A[p] = v$.
You must perform these queries in the order given in the input. In particular, each query of type 'q' must consider all updates of type 'u' that precede the query.
Write a program to solve this problem efficiently.
Input
First line contains two integers $n$ and $q$ ($1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$), the number of elements of the array and the number of queries to answer, respectively. The second line contains $n$ integers representing the initial content of the array. Each $A[i]$ value of the array satisfies the constraint $1\leq A[i] \leq 10^9 $. The next $q$ lines contain a character 'q' or 'u' and two integers, separated by spaces.
- If the character is 'q', the query is in the format q i j, where $1 \leq i \leq j \leq N$.
- If the character is 'u', the query is in the format u p v, where $1 \leq p \leq N$ and $1 \leq v \leq 10^9$.
Output
For each query of type 'q', print a line with the answer. You must answer the queries in the order given in the input.
Sample test(s)
Input
5 6
12 4 2 3 8
q 1 2
u 3 30
q 3 5
u 1 10
u 3 9
q 1 5
Output
1
2
5
Input
5 9
10 2 32 18 54
q 1 5
u 1 5
q 1 5
u 2 4
q 1 5
u 3 3
q 1 5
u 4 2
q 1 5
Output
3
2
2
2
3