Given an array $a$, consisting of small integers $(1≤a_i≤40)$. You need to build a data structure that processes two types of queries:

1. find the number of inversions on a segment,
2. change the element of the array.

The first line contains two integers $n,q$, the length of the array and the number of queries, respectively $(1≤n,q≤10^5)$.

The second line contains $n$ numbers $a_1, ..., a_n$, where $a_i$ is the initial state of the array $(1≤a_i≤40)$.

The following $q$ lines describe the queries. Each of these lines has the format "type{_i} $x_i$ $y_i$".

If type$_i=1$, then in the $i$-th query you need to find the number of inversions on a segment from $x_i$ to $y_i$, inclusive (in this case $1≤x_i≤y_i≤n$).

If type$_i=2$, then the element with the index $x_i$ is set to $y_i$ (in this case $1≤x_i≤n,\ 1≤y_i≤40$).

For each request of type 1 print the answer to this request on a separate line.