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

const int N = 2e5 + 5;

int n, q, a[N], Left[N][9];

int solve(int l, int k) {
	if (k <= 8) {
		return Left[l][k];
	}
	return abs(solve(l, k - 1) - solve(l + (1 << k - 1), k - 1));
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		Left[i][0] = a[i];
	}
	for (int j = 1; j <= 8; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			Left[i][j] = abs(Left[i][j - 1] - Left[i + (1 << j - 1)][j - 1]);
		}
	}
	for (int i = 1; i <= q; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, v;
			cin >> x >> v;
			a[x] = v;
			Left[x][0] = a[x];
			for (int j = 1; j <= 8; j++) {
				for (int i = x - (1 << j) + 1; i <= x; i++) {
					Left[i][j] = abs(Left[i][j - 1] - Left[i + (1 << j - 1)][j - 1]);
				}
			}
		} else {
			int l, k;
			cin >> l >> k;
			cout << solve(l, k) << '\n';
		}
	}

	return 0;
}