CF679E.Bear and Bad Powers of 42

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.

Limak 是一只熊，不擅长处理查询，因此他请你代为完成。

我们称 42 的幂（即数字 $1,\,42,\,1764,\,\dots$）为“坏数”，其余所有数均为“好数”。

给定一个由 $n$ 个好数组成的序列 $t_1,\,t_2,\,\dots,\,t_n$。你需要处理 $q$ 个三种类型的查询：

1. 1 i — 单独一行输出 $t_i$。
2. 2 a b x — 对于满足 $a \le i \le b$ 的每个 $i$，将 $t_i$ 设为 $x$。保证 $x$ 是一个好数。
3. 3 a b x — 对于满足 $a \le i \le b$ 的每个 $i$，将 $t_i$ 增加 $x$；此后，只要存在某个 $t_i$ 是坏数，就重复该过程（即持续对所有坏的 $t_i$ 加上 $x$，直到全部变为好数为止）。

注意：每次查询执行完毕后，所有 $t_i$ 均为好数。

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 _t_1, _t_2, ..., t__n (2 ≤ t__i ≤ 109) — 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 ≤ 109) is guaranteed to be good.

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

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100\,000$）——分别表示 Limak 序列的长度和查询的数量。

输入的第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$2 \leq t_i \leq 10^9$）——表示 Limak 序列的初始元素。所有 $t_i$ 均为“好”的数。

接下来是 $q$ 行，每行描述一次查询。第 $i$ 行对应第 $i$ 次查询。该行的第一个数是一个整数 $\text{type}_i$（$1 \leq \text{type}_i \leq 3$）——表示查询的类型。至少存在一次类型为 1 的查询，因此输出不会为空。

在类型为 2 和类型为 3 的查询中，保证有 $1 \leq a \leq b \leq n$。

在类型为 2 的查询中，给定的整数 $x$（$2 \leq x \leq 10^9$）保证是“好”的数。

在类型为 3 的查询中，给定的整数 $x$（$1 \leq x \leq 10^9$）可能是“坏”的数。

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

对于每个第一类查询，请在单独一行中输出答案。

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.

查询 3 2 4 42 后，序列为：$40,\,1742,\,49,\,1714,\,4,\,1722$。

查询 3 2 6 50 后，序列为：$40,\,1842,\,149,\,1814,\,104,\,1822$。

查询 2 3 4 41 后，序列为：$40,\,1842,\,41,\,41,\,104,\,1822$。

查询 3 1 5 1 后，序列为：$43,\,1845,\,44,\,44,\,107,\,1822$。