const
   MaxN = 1 shl 18;


var
   inFile, outFile : text;
   N, Q, X, Y, Z, sol : longint;
   a : array[0..MaxN] of longint;
   t, l, r : array[0..2*MaxN] of longint;
   N1, offset : longint;
   i, rs, ls : longint;


function gcd(a, b : longint) : longint;
begin
   if (b = 0) then gcd := a
	      else gcd := gcd(b, a MOD b);
end;


procedure init(n : longint);
var
   i, node : longint;

begin
   N1 := n;
   offset := MaxN - 1;
   for i := 1 to 2 * MaxN - 1 do t[i] := 1;

   for i := 1 to n do
      t[i + offset] := a[i];

   for i := offset + 1 to 2 * MaxN - 1 do begin
      l[i] := i;
      r[i] := i;
   end;

   for node := offset downto 1 do begin
      t[node] := gcd(t[2 * node], t[2 * node + 1]);
      l[node] := l[2 * node];
      r[node] := r[2 * node + 1];
   end;
end;


procedure update(pos, val : longint);
var
   i : longint;

begin
   i := pos + offset;
   t[i] := val;
   i := i div 2;
   while (i > 0) do begin
      t[i] := gcd(t[2 * i], t[2 * i + 1]);
      i := i div 2;
   end;
end;



function firstRight(pos, k : longint) : longint;
var
   i : longint;
   found : boolean;

begin
   i := pos + offset;
   found := false;
   while ((i > 1) AND (t[i] MOD k = 0) AND (NOT found)) do begin
      if ((pos + offset) <= l[i DIV 2])
         then i := i DIV 2
      else
         i := r[i] + 1;
      if (i > offset + N1) then found := true;
   end;

   if (NOT found) then begin
      while (i <= offset) do
         if (t[2 * i] MOD k = 0) then i := 2 * i + 1
         else i := 2 * i;
   end;

   if (NOT found) then firstRight := i - offset - 1
   else firstRight := N1;
end;



function firstLeft(pos, k : longint) : longint;
var
   i : longint;
   found : boolean;

begin
   i := pos + offset;
   found := false;
   while ((i > 1) AND (t[i] MOD k = 0) AND (NOT found)) do begin
      if ((pos + offset) >= r[i DIV 2])
         then i := i DIV 2
      else begin
         i := l[i] - 1;
         if (i <= offset) then found := true;
      end;
   end;

   if (NOT found) then begin
      while (i <= offset) do
         if (t[2 * i + 1] MOD k = 0) then i := 2 * i
         else i := 2 * i + 1;
   end;

   if (NOT found) then firstLeft := i - offset + 1
   else firstLeft := 1;
end;



begin

        assign(inFile, 'metro.in'); reset(inFile);
	assign(outFile, 'metro.out'); rewrite(outFile);
	
	read(inFile, N, Q);
	for i := 1 to N do
           read(inFile, a[i]);

        init(N);
	
	for i := 1 to Q do begin

           read(inFile, X, Y, Z);
           if (X = 1) then update(Y, Z)
           else begin
              ls := firstLeft(Y, Z);
              rs := firstRight(Y, Z);
	      writeln(outFile, rs - ls + 1);
	   end;
	
        end;

	close(inFile);
	close(outFile);	

end.