#include <cstdlib>
#include <cstdio>
#include <memory.h>

const int MaxN = 1 << 18;  // 2^18

int N, Q, X, Y, Z, sol;
int a[MaxN];

int gcd(int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

struct SegmentTree {
	int N;
	int t[2 * MaxN];
	int l[2 * MaxN];
	int r[2 * MaxN];
	int offset;
		
	void init(int a[], int n) {
		N = n;
		offset = MaxN - 1;
		for (int i = 1; i < 2 * MaxN; i++) t[i] = 1;

		for (int i = 1; i <= n; i++)
			t[i + offset] = a[i];
		for (int i = offset + 1; i < 2 * MaxN; i++) {
			l[i] = i;  r[i] = i;
		}

		for (int node = offset; node > 0; node--) {
			t[node] = gcd(t[2 * node], t[2 * node + 1]);
			l[node] = l[2 * node];
			r[node] = r[2 * node + 1];
		}
	}

	void update(int pos, int val) {
		int i = pos + offset;
		t[i] = val;
		i = i / 2;
		while (i > 0) {
			t[i] = gcd(t[2 * i], t[2 * i + 1]);
			i = i / 2;
		}
	}

	int firstRight(int pos, int k) {
		int i = pos + offset;
		while (i > 1 && t[i] % k == 0) {
			if (pos + offset <= l[i / 2])
				i = i / 2;
			else
				i = r[i] + 1;
			if (i > offset + N) return N;
		}

		while (i <= offset) {
			if (t[2 * i] % k == 0)
				i = 2 * i + 1;
			else
				i = 2 * i;
		}
		return i - offset - 1;
	}

	int firstLeft(int pos, int k) {
		int i = pos + offset;
		while (i > 1 && t[i] % k == 0) {
			if (r[i / 2] <= pos + offset)
				i = i / 2;
			else {
				i = l[i] - 1;
				if (i <= offset) return 1;
			}
		}

		while (i <= offset) {
			if (t[2 * i + 1] % k == 0)
				i = 2 * i;
			else
				i = 2 * i + 1;
		}
		return i - offset + 1;
	}

} metroLine;

int main() {

	FILE* inFile = fopen("metro.in", "r");
	FILE* outFile = fopen("metro.out", "w");

	fscanf(inFile, "%d%d", &N, &Q);
	for (int i = 1; i <= N; i++)
		fscanf(inFile, "%d", &a[i]);

	metroLine.init(a, N);
	for (int i = 0; i < Q; i++) {
		fscanf(inFile, "%d%d%d", &X, &Y, &Z);
		if (X == 1)
			metroLine.update(Y, Z);
		else {
			int r = metroLine.firstRight(Y, Z);
			int l = metroLine.firstLeft(Y, Z);
			fprintf(outFile, "%d\n", r - l + 1);
		}
	}

	fclose(inFile);
	fclose(outFile);
	return 0;
}