Bear and Bad Powers of 42

题意翻译

定义一个正整数是坏的，当且仅当它是 $42$ 的次幂，否则它是好的。 给定一个长度为 $n$ 的序列 $a_i$，保证初始时所有数都是好的。 有 $q$ 次操作，每次操作有三种可能： - `1 i` 查询 $a_i$。 - `2 l r x` 将 $a_{l\dots r}$ 赋值为一个好的数 $x$。 - `3 l r x` 将 $a_{l \dots r}$ 都加上 $x$，重复这一过程直到所有数都变好。 $n,q \le 10^5$，$a_i,x \le 10^9$。

题目描述

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 $ t_{1},t_{2},...,t_{n} $ . Your task is to handle $ q $ queries of three types: 1. 1 i — print $ t_{i} $ in a separate line. 2. 2 a b x — for  set $ t_{i} $ to $ x $ . It's guaranteed that $ x $ is a good number. 3. 3 a b x — for  increase $ t_{i} $ by $ x $ . After this repeat the process while at least one $ t_{i} $ is bad. You can note that after each query all $ t_{i} $ are good.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ q $ ( $ 1<=n,q<=100000 $ ) — the size of Limak's sequence and the number of queries, respectively. The second line of the input contains $ n $ integers $ t_{1},t_{2},...,t_{n} $ ( $ 2<=t_{i}<=10^{9} $ ) — initial elements of Limak's sequence. All $ t_{i} $ 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 $ type_{i} $ ( $ 1<=type_{i}<=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<=10^{9} $ ) is guaranteed to be good. In queries of the third type an integer $ x $ ( $ 1<=x<=10^{9} $ ) may be bad.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

1742
49
1842
1814
1822
43
44
107

说明

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 $ .