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 <image> set ti to x. It's guaranteed that x is a good number. 
  3. 3 a b x — for <image> 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

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

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

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


Output

1742
49
1842
1814
1822
43
44
107

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.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
const int shit = 42;
struct node {
  long long mx, mn, lazy, ladd, mn_diff;
  node() {
    mx = 0;
    mn = 1e16;
    lazy = -1;
    ladd = 0;
    mn_diff = 1e16;
  }
};
long long a[maxn], tmpval, tmpnex, tmpaddval;
node seg[maxn * 4], void_node;
vector<long long> bads;
inline node merge(node a, node b) {
  node c;
  c.mx = max(a.mx, b.mx);
  c.mn = min(a.mn, b.mn);
  c.mn_diff = min(a.mn_diff, b.mn_diff);
  return c;
}
inline long long get_next(long long x) {
  return *lower_bound(bads.begin(), bads.end(), x);
}
inline void build(int s, int e, int v) {
  if (e - s < 2) {
    seg[v].mx = seg[v].mn = a[s];
    seg[v].mn_diff = get_next(a[s]) - a[s];
    return;
  }
  int m = (s + e) / 2;
  build(s, m, 2 * v);
  build(m, e, 2 * v + 1);
  seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
}
inline void shift(int s, int e, int v) {
  if (e - s >= 2) {
    if (seg[v].lazy != -1) {
      seg[2 * v].ladd = seg[2 * v + 1].ladd = seg[v].ladd;
      seg[2 * v].lazy = seg[2 * v + 1].lazy = seg[v].lazy;
      seg[2 * v].mn = seg[2 * v].mx = seg[2 * v + 1].mx = seg[2 * v + 1].mn =
          seg[v].ladd + seg[v].lazy;
      seg[2 * v].mn_diff = seg[2 * v + 1].mn_diff = seg[v].mn_diff;
    } else if (seg[v].ladd) {
      seg[2 * v].ladd += seg[v].ladd;
      seg[2 * v + 1].ladd += seg[v].ladd;
      seg[2 * v].mn += seg[v].ladd;
      seg[2 * v + 1].mn += seg[v].ladd;
      seg[2 * v].mx += seg[v].ladd;
      seg[2 * v + 1].mx += seg[v].ladd;
      if (seg[v].mx == seg[v].mn)
        seg[2 * v].mn_diff = seg[2 * v + 1].mn_diff = seg[v].mn_diff;
      else {
        seg[2 * v].mn_diff -= seg[v].ladd;
        seg[2 * v + 1].mn_diff -= seg[v].ladd;
      }
    }
  }
  seg[v].ladd = 0;
  seg[v].lazy = -1;
}
inline node get(int l, int r, int s, int e, int v) {
  if (l <= s && e <= r) return seg[v];
  if (r <= s || e <= l) return void_node;
  shift(s, e, v);
  int m = (s + e) / 2;
  return merge(get(l, r, s, m, 2 * v), get(l, r, m, e, 2 * v + 1));
}
inline void add(int l, int r, int s, int e, int v) {
  if (l <= s && e <= r) {
    if (seg[v].mn_diff >= tmpaddval) {
      seg[v].ladd += tmpaddval;
      seg[v].mn += tmpaddval;
      seg[v].mx += tmpaddval;
      seg[v].mn_diff -= tmpaddval;
      return;
    } else if (seg[v].mx == seg[v].mn) {
      seg[v].ladd += tmpaddval;
      seg[v].mn += tmpaddval;
      seg[v].mx += tmpaddval;
      long long nex = get_next(seg[v].mx);
      seg[v].mn_diff = nex - seg[v].mx;
      return;
    }
  }
  if (r <= s || e <= l) return;
  shift(s, e, v);
  int m = (s + e) / 2;
  add(l, r, s, m, 2 * v);
  add(l, r, m, e, 2 * v + 1);
  seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
}
inline void st(int l, int r, int s, int e, int v) {
  if (l <= s && e <= r) {
    seg[v].lazy = tmpval;
    seg[v].ladd = 0;
    seg[v].mx = seg[v].mn = tmpval;
    seg[v].mn_diff = tmpnex - tmpval;
    return;
  }
  if (r <= s || e <= l) return;
  shift(s, e, v);
  int m = (s + e) / 2;
  st(l, r, s, m, 2 * v);
  st(l, r, m, e, 2 * v + 1);
  seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long p = 1;
  while (p < 1e17) bads.push_back(p), p *= shit;
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(0, n, 1);
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int pos;
      cin >> pos;
      pos--;
      node x = get(pos, pos + 1, 0, n, 1);
      cout << x.mx << endl;
    } else if (type == 2) {
      long long l, r, x;
      cin >> l >> r >> x;
      l--;
      tmpnex = get_next(x);
      tmpval = x;
      st(l, r, 0, n, 1);
    } else {
      long long l, r, x;
      cin >> l >> r >> x;
      l--;
      tmpaddval = x;
      add(l, r, 0, n, 1);
      while (get(l, r, 0, n, 1).mn_diff == 0) add(l, r, 0, n, 1);
    }
  }
}
