smoothie-web Problems Contests Ranking About

# BSSPC 2020 P10 - nani

## Problem Statement

Suppose you're given an array of size $N$ ($1\leq N\leq 10^5$). This array contains integers $a_1,\ldots,a_N$, where the elements satisfy $0 for each $i$. For each $a_i$, its initial value is $1$.

You need to answer $Q$ queries in total, where $1\leq Q\leq 10^5$. There are two types of queries:

• query l r: Output the value of $\left( \prod_{i=l}^r a_i \right)\text{ mod } 10$, where $\prod_{i=l}^r a_i$ is the product of every element in the subarray $a_l$ to $a_r$. For this type of query, we have $1\leq l.

• update idx val: Update the value of $a_\texttt{idx}$ to val. For this type of query, the parameters satisfy $1\leq \texttt{idx}\leq N$ and $0<\texttt{val}<10^9$.

## Input Specification

The first line contains the integers $N$ and $Q$, separated by a space.

On each of the next $Q$ 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 $(14\times 9) \text{ mod } 10=6$
update 4 11 [14, 9, 1, 11, 1]
query 2 4 [14, 9, 1, 11, 1] The output should be $(9\times 11)\text{ mod } 10=9$

## 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] $(2\times 3\times 4)\text{ mod }10=4$
query 3 5 [5, 2, 3, 4, 1, 1] $(3\times 4\times 1)\text{ mod }10=2$
query 1 5 [5, 2, 3, 4, 1, 1] $(5\times 2\times 3\times 4\times 1)\text{ mod }10=0$