Bear and Bad Powers of 42
Contest: Codeforces Round 356 (Div. 1)
Difficulty rating: 3100
Tags: data structures

Limak, a bear, isn't good at handling queries. So, he asks you to do it.

We say that powers of 42 (numbers 1, 42, 1764, ...) are bad. Other numbers are good.

You are given a sequence of n good integers t1, t2, ..., tn. Your task is to handle q queries of three types:

1. 1 i — print ti in a separate line.
2. 2 a b x — for $$i \in [a,b]$$ set ti to x. It's guaranteed that x is a good number.
3. 3 a b x — for $$i \in [a,b]$$ increase ti by x. After this repeat the process while at least one ti is bad.

You can note that after each query all ti are good.

Input format:
The first line of the input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the size of Limak's sequence and the number of queries, respectively.

The second line of the input contains n integers t1, t2, ..., tn (2 ≤ ti ≤ 109) — initial elements of Limak's sequence. All ti are good.

Then, q lines follow. The i-th of them describes the i-th query. The first number in the line is an integer typei (1 ≤ typei ≤ 3) — the type of the query. There is at least one query of the first type, so the output won't be empty.

In queries of the second and the third type there is 1 ≤ a ≤ b ≤ n.

In queries of the second type an integer x (2 ≤ x ≤ 109) is guaranteed to be good.

In queries of the third type an integer x (1 ≤ x ≤ 109) may be bad.

Output format:
For each query of the first type, print the answer in a separate line.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
After a query 3 2 4 42 the sequence is 40, 1742, 49, 1714, 4, 1722.

After a query 3 2 6 50 the sequence is 40, 1842, 149, 1814, 104, 1822.

After a query 2 3 4 41 the sequence is 40, 1842, 41, 41, 104, 1822.

After a query 3 1 5 1 the sequence is 43, 1845, 44, 44, 107, 1822.

Example input:
6 12
40 1700 7 1672 4 1722
3 2 4 42
1 2
1 3
3 2 6 50
1 2
1 4
1 6
2 3 4 41
3 1 5 1
1 1
1 3
1 5

Example output:
1742
49
1842
1814
1822
43
44
107

Editorial:
Tutorial below
. . . . . . . . . . . . . . . . . . .
Let's first solve the problem without queries "in the interval change all numbers to x". Then, we can make a tree with operations (possible with lazy propagation):
• add on the interval
• find minimum in the whole tree
In a tree for each index $$i \in [1,n]$$ let's keep the distance to the next power of 10. After each "add on the interval" we should find the minimum and check if it's positive. If not then we should change value of the closest power of 10 for this index, and change the value in the tree. Then, we should again find the minimum in the tree, and so on. The amortized complexity is O((n + q) * log(n) * log10(values)). It can be proved that numbers won't exceed (n + q) * 1e9 * log, but please check it by yourself Gleb.
Now let's think about the remaining operation of changing all interval to some value. We can set only one number (the last one) to the given value, and set other values to INF. We want to guarantee that if t[i] ≠ t[i + 1] then the i-th value is correctly represented in the tree. Otherwise, it can be INF instead (or sometimes it may be correctly represented, it doesn't bother me). When we have the old query of type "add something to interval [a, b]" then if index a - 1 or index b contains INF in the tree then we should first retrieve the true value there. You can see that each operation changes O(1) values from INF to something finite. So, the amortized complexity is still O((n + q) * log(n) * log10(values).
One thing regarding implementation. In my solution there is "set < int > interesting" containing indices with INF value. I think it's easier to implemement the solution with this set.