E - Counting multiples

Time limit: 6 s
Memory limit: 2048 MiB
Languages: C, C++, Java, Python, ... (details)

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