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*<sub class="lower-index">1</sub>, *t*<sub class="lower-index">2</sub>, ..., *t*<sub class="lower-index">*n*</sub>. Your task is to handle *q* queries of three types:
 1.  1 i — print *t*<sub class="lower-index">*i*</sub> in a separate line. 1.  2 a b x — for <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/dfe3c7c46edb4f485631cb422ffc55ec2c0ae0a7.png" style="max-width: 100.0%;max-height: 100.0%;"/> set *t*<sub class="lower-index">*i*</sub> to *x*. It's guaranteed that *x* is a good number. 1.  3 a b x — for <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/dfe3c7c46edb4f485631cb422ffc55ec2c0ae0a7.png" style="max-width: 100.0%;max-height: 100.0%;"/> increase *t*<sub class="lower-index">*i*</sub> by *x*. After this repeat the process while at least one *t*<sub class="lower-index">*i*</sub> is bad. 
You can note that after each query all *t*<sub class="lower-index">*i*</sub> are good.
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*<sub class="lower-index">1</sub>, *t*<sub class="lower-index">2</sub>, ..., *t*<sub class="lower-index">*n*</sub> (2 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — initial elements of Limak's sequence. All *t*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">*i*</sub> (1 ≤ *type*<sub class="lower-index">*i*</sub> ≤ 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<sup class="upper-index">9</sup>) is guaranteed to be good.

In queries of the third type an integer *x* (1 ≤ *x* ≤ 10<sup class="upper-index">9</sup>) may be bad.
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 <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
// #include <bitset>
const int oo=2139063143;
const int N=1010000;
const int P=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
	if (x< 0) putchar('-'),x=-x;
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
LL m[20];
LL get (LL x)
{
	if (x> m[11]) return 1e18;
	int L=-1,R=11;
	while (L+1< R)
	{
		int mid=(L+R)>>1;
		if (x<=m[mid]) R=mid;
		else L=mid;
	}
	return m[R]-x;
}
struct TREE { LL w,d,mi; }t[N<<2];
#define w(p) t[p].w
#define d(p) t[p].d
#define mi(p) t[p].mi
int a[N];
void build (int p,int l,int r)
{
	if (l==r) return w(p)=a[l],mi(p)=get (a[l]),void ();
	int mid=(l+r)>>1,ls=p<<1,rs=ls|1;
	build (ls,l,mid),build (rs,mid+1,r);
	mi(p)=min (mi(ls),mi(rs));
}
void pushd (int p,LL d) { d(p)+=d,mi(p)-=d; }
void pushw (int p,LL d) { w(p)=d,d(p)=0,mi(p)=get (d); }
void push (int p)
{
	int ls=p<<1,rs=ls|1;
	if (w(p)) pushw (ls,w(p)),pushw (rs,w(p)),w(p)=0;
	if (d(p)) pushd (ls,d(p)),pushd (rs,d(p)),d(p)=0;
}
void change (int p,int l,int r,int L,int R,int op,LL d)
{
	if (L<=l&&r<=R) return op?pushd (p,d):pushw (p,d),void ();
	int mid=(l+r)>>1,ls=p<<1,rs=ls|1; push (p);
	if (L<=mid) change (ls,l,mid,L,R,op,d);
	if (R> mid) change (rs,mid+1,r,L,R,op,d);
	mi(p)=min (mi(ls),mi(rs));
}
LL query (int p,int l,int r,int w)
{
	if (l==r) return w(p)+d(p);
	int mid=(l+r)>>1,ls=p<<1,rs=ls|1; push (p);
	return (w<=mid)?query (ls,l,mid,w):query (rs,mid+1,r,w);
}
void rebuild (int p,int l,int r)
{
	if (l==r) return mi(p)=get (w(p)+d(p)),void ();
	if (mi(p)>=0) return ;
	int mid=(l+r)>>1,ls=p<<1,rs=ls|1; push (p);
	rebuild (ls,l,mid),rebuild (rs,mid+1,r);
	mi(p)=min (mi(ls),mi(rs));
}
int main ()
{
	// freopen (".in","r",stdin);
	// freopen (".out","w",stdout);
	m[0]=1;
	for (int i=1; i<=11; i++)
		m[i]=m[i-1]*42;
	int n,q; sc(n),sc(q);
	for (int i=1; i<=n; i++)
		sc(a[i]);
	build (1,1,n);
	while (q--)
	{
		int op,l,r,x; sc(op);
		if (op==1) sc(x),pr(query (1,1,n,x));
		else
		{
			sc(l),sc(r),sc(x);
			if (op==2) change (1,1,n,l,r,0,x);
			else
			{
				do change (1,1,n,l,r,1,x),rebuild (1,1,n);
				while (!mi(1));
			}
		}
	}

	return 0;
}
