# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## A Journey to Rupsha

Tomorrow, **April 14th, 2019** is a special day. Guess why.

**Bengali New Year?**

Your guess was partially correct. But there’s another reason. Tomorrow, the season 8 of the epic fantasy TV series **Game of Thrones** will be premiered on **HBO**. This is the final season of the series.

For those, who don’t know about the series, we won’t give you any spoiler. So, you can assume that the problem statement is spoiler free.

**Ramsay Bolton** and **Theon Greyjoy** are best friends. They live in a small town named **Teligati**. The city is located at the center of the North.
One day they decided to visit the city **Rupsha** which is far south form the wall.

On their journey, they found some mysterious places. One of them is **Fulbari Gate**. To pass **Fulbari Gate** they need to break a chain which consists of some heavy locks. Breaking the chain is very tough. To do this, they need to perform some operations on the locks of the chain.

You are a free folk and they requested you to help them in this situation.

You are given the chain **A** which contains **N** locks.

You need to perform **Q** queries of the following two types:

**Multiply l r** — multiply **3 ^{0}** with

**A**,

_{l}**3**with

^{1}**A**,

_{l + 1}**3**with

^{2}**A**, ……. ,

_{l + 2}**3**with

^{(r - l)}**A**.

_{r}**Ask x** — print the value of the lock **A _{x}** with modulo

**10**.

^{9}+7### Input

The first line contains two integers **N** and **Q** **( 1 ≤ N ≤ 10 ^{5} , 1 ≤ Q ≤ 10^{5} )** — the number of elements in array

**A**and the number of queries.

The second line contains **n** integers **a _{1},a_{2},…,a_{n}**

**(1 ≤ a**— the locks of chain

_{i}≤ 10^{18})**A**.

Then **q** lines follow, describing queries in the format given in the statement.
**Multiply l r ( 1 ≤ l ≤ r ≤ n)** — denotes a multiplication query.
**Ask x (1 ≤ x ≤ n)** — denotes a query on the value of the lock of index **x**.

### Output

For each Ask query, print the answer to it.

### Samples

Input | Output |
---|---|

5 5 4 5 4 7 10 Multiply 1 5 Ask 1 Multiply 2 5 Ask 3 Ask 5 | 4 108 21870 |

For your information,

**Theon Greyjoy** and **Ramsay Bolton**

Login to submit