A Journey to Rupsha

Intra KUET Programming Co...
Limits 1s, 512 MB

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 AA which contains NN locks.

You need to perform QQ queries of the following two types:

Multiply l r — multiply 303^0 with AlA_l, 313^1 with Al+1A_{l + 1}, 323^2 with Al+2A_{l + 2}, …, 3rl3^{r - l} with ArA_r.

Ask x — print the value of the lock AxA_x with modulo 109+710^9+7.

Input

The first line contains two integers NN and QQ (1N1051 ≤ N ≤ 10^5, 1Q1051 ≤ Q ≤ 10^5) — the number of elements in array A and the number of queries.

The second line contains n integers a1a_1, a2a_2, …, ana_n (1ai10181 ≤ a_i ≤ 10^{18}) — the locks of chain AA.

Then q lines follow, describing queries in the format given in the statement.

Multiply l r (1lrn1 ≤ l ≤ r ≤ n) — denotes a multiplication query.

Ask x (1xn1 ≤ x ≤ n) — denotes a query on the value of the lock of index xx.

Output

For each Ask query, print the answer to it.

Sample

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

Submit

Login to submit.

Contributors

Statistics

79% Solution Ratio
ZeronfinityEarliest, Apr '19
mahabub.tweetFastest, 0.0s
Rawaha0909Lightest, 1.5 MB
serotoninShortest, 1266B
Toph uses cookies. By continuing you agree to our Cookie Policy.