#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
#define vvvll vector<vector<vector<ll>>>
#define vvll vector<vector<ll>>
#define vll vector<ll>

constexpr ll INF = (1ll << 60);
constexpr ll mod = 1000000007;
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

ll V;
ll G[20][20];
ll dp[200000][20];
int main() {
    ll x[20],y[20],z[20];
    cin >> V;
    rep(i, V) {
        cin>>x[i]>>y[i]>>z[i];
    }
    rep(i,V){
        rep(j,V){
            G[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j])+max(0ll,z[j]-z[i]);
        }
    }
    rep(i, 1 << V) {
        rep(j, 20) { dp[i][j] = INF; }
    }
    dp[0][0] = 0;
    rep(S, 1 << V) {
        rep(v, V) {
            rep(u, V) {
                if (S != 0 && !(S & (1 << u))) continue; // u を含まない場合を除く
                if ((S & (1 << v)) == 0) {
                    if (v != u) chmin(dp[S | (1 << v)][v], dp[S][u] + G[u][v]);
                }
            }
        }
    }
    if (dp[(1 << V) - 1][0] != INF) {
        cout << dp[(1 << V) - 1][0] << endl;
    }
    return 0;
}
#include <cstdio>
#include <iostream>
#define N 300005

using namespace std;

long long val[N];

inline long long read()
{
	long long f(1),x(0);char a=getchar();
	while(a!='-'&&(a<'0')||a>'9')a=getchar();
	a=='-'?f=-1:x=a-'0';a=getchar();
	while(a>='0'&&a<='9')x=(x<<3)+(x<<1)+a-'0',a=getchar();
	return x*f;
}

struct node
{
	long long val,lazy,l,r;
}tree[N<<2];

void build(long long root,long long l,long long r)
{
	tree[root].l=l;tree[root].r=r;
	if(l==r)
	{
		tree[root].val=val[r];
		return;
	}
	long long mid=(l+r)/2;
	build((root<<1),l,mid);build((root<<1)+1,mid+1,r);
	tree[root].val=tree[(root<<1)].val ^ tree[(root<<1)+1].val;
}

void pushdown(long long root)
{
	if(tree[root].lazy)
	{
		tree[(root<<1)  ].lazy^=tree[root].lazy;
		tree[(root<<1)+1].lazy^=tree[root].lazy;
		tree[(root<<1)  ].val^=tree[root].lazy*(tree[(root<<1)  ].r-tree[(root<<1)  ].l+1);
		tree[(root<<1)+1].val^=tree[root].lazy*(tree[(root<<1)+1].r-tree[(root<<1)+1].l+1);
		tree[root].lazy=0;
	}
}

void update(long long root,long long l,long long r,long long val)
{
	if(tree[root].l>r||tree[root].r<l)return;
	if(tree[root].r<=r&&tree[root].l>=l)
	{
		tree[root].lazy^=val;
		tree[root].val^=val*(tree[root].r-tree[root].l+1);
		return;
	}
	pushdown(root);
	update((root<<1),l,r,val);update((root<<1)+1,l,r,val);
	tree[root].val=tree[(root<<1)].val^tree[(root<<1)+1].val;
}

long long queryval(long long root,long long l,long long r)
{    
	if(tree[root].l>r||tree[root].r<l)return 0;
	if(tree[root].r<=r&&tree[root].l>=l)return tree[root].val;
	pushdown(root);
	return queryval((root<<1),l,r)^queryval((root<<1)+1,l,r);
}

int main()
{
	long long n,m;
	n=read();m=read();
	for(int i=1;i<=n;i++)val[i]=read();
	build(1,1,n);
	while(m--)
	{
		long long opt=read();
		if(opt==1)
		{
			long long x=read(),k=read();
			update(1,x,x,k);
		}
		else
		{
			long long x=read(),y=read();
			printf("%lld\n",queryval(1,x,y));
		}
	}
	return 0;
}