#include <bits/stdc++.h>
 
#define fst first
#define snd second
#define ll long long
#define ld long double
#define pb push_back
#define emp emplace_back
#define pii pair<int, int>
#define usg unsigned
#define sg signed
#define mp make_pair
 
using namespace std;
 
void setIO(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}
 
const ld PI = 4*atan((ld)1);
const int INF = 1e9+7;
 
class SegmentTree
{
private:
	int n;
	vector<ll>a;
	vector<ll>t;
private:
	void build(int i, int l, int r){
		if (l == r){
			t[i] = a[l];
			return;
		}
		int m = (l+r)>>1;
		build(i<<1, l, m);
		build(i<<1|1, m+1, r);
		t[i] = (t[i<<1]^t[i<<1|1]);
	}
 
	void updatePoint(int i, int l, int r, int pos, int v){
		if (l == r){
			t[i] ^= v;
			return;
		}
		int m = (l+r)>>1;
		if (pos <= m) updatePoint(i<<1, l, m, pos, v);
		else updatePoint(i<<1|1, m+1, r, pos, v);
		t[i] = (t[i<<1]^t[i<<1|1]);
	}
 
	int XORsum(int i, int l, int r, int pl, int pr){
		if (l >= pl && r <= pr)
			return t[i];
		if (pl > r || pr < l)
			return 0;
		int m = (l+r)>>1;
		return (XORsum(i<<1, l, m, pl, pr)^XORsum(i<<1|1, m+1, r, pl, pr));
	}
 
public:
	SegmentTree(const vector<ll> &_A){
		a = _A; n = a.size();
		t.assign(n<<2, 0);
		build(1, 0, n-1);
	}
 
	void PointUpdate(int pos, int val){
		updatePoint(1, 0, n-1, pos-1, val);
	}
 
	int XORsum(int l, int r){
		return XORsum(1, 0, n-1, l-1, r-1);
	}
};
 
vector<ll>v;
 
int main(){
	setIO();
	int n, q;
	cin >> n >> q;
	v.resize(n);
	for (auto &x : v)
		cin >> x;
	SegmentTree St(v);
	for (int i = 0; i < q; i++){
		int t, l, r;
		cin >> t >> l >> r;
		if (t&1) St.PointUpdate(l, r);
		else cout << St.XORsum(l, r) << endl;
	}
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll> ;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define inf 1LL<<60;
ll min(ll a,ll b){return a>=b ? b:a;}
ll max(ll a,ll b){return a>=b ? a:b;}

ll dist[1<<18];

typedef struct{
    ll to;
    ll c;
    ll d;
}town;

vector<town> G[1LL<<18];

ll func(ll t,ll d){
    ll rd=sqrt(d);
    ll ret=d/(t+1);
    for (ll i=-10;i<=10;++i){
        if (rd+i-t-1<0) continue;
        ll k=rd-t+i-1+d/(rd+i);
        ret=min(ret,k);
    }
    return ret;
}

void dijkstra(ll st){
    priority_queue<P,vector<P>,greater<>> q;
    dist[st]=0;
    q.push(P(0,st));
    while (!q.empty()){
        ll D=q.top().first;
        ll pos=q.top().second;q.pop();
        if (dist[pos]!=D) continue;
        rep(i,(ll)G[pos].size()){
            ll to=G[pos][i].to;
            ll cost=G[pos][i].c;
            ll di=G[pos][i].d;
            ll ct=func(dist[pos],di);
            if (dist[to]>dist[pos]+ct+cost){
                dist[to]=ct+cost+dist[pos];
                q.push(make_pair(dist[to],to));
            }
        }
    }
}

int main(){
    ll n,m;
    cin >> n >> m;
    rep(i,m){
        ll a,b,c,d;
        cin >> a >> b >> c >>d;
        a--;b--;
        G[a].push_back(town({b,c,d}));
        G[b].push_back(town({a,c,d}));
    }
    rep(i,n+1) dist[i]=1LL<<60;
    dijkstra(0);
    if (dist[n-1]==1LL<<60){
        cout << -1 << endl;
    }
    else cout << dist[n-1] << endl;
}





