Bash likes playing with arrays. He has an array a1, a2, ... an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.

Suppose he guesses that the gcd of the elements in the range [l, r] of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself.

Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process q queries of one of the following forms:

  * 1 l r x — Bash guesses that the gcd of the range [l, r] is x. Report if this guess is almost correct. 
  * 2 i y — Bash sets ai to y. 



Note: The array is 1-indexed.

Input

The first line contains an integer n (1 ≤ n ≤ 5·105) — the size of the array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

The third line contains an integer q (1 ≤ q ≤ 4·105) — the number of queries.

The next q lines describe the queries and may have one of the following forms:

  * 1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109). 
  * 2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 109). 



Guaranteed, that there is at least one query of first type.

Output

For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.

Examples

Input

3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2


Output

YES
YES
NO


Input

5
1 2 3 4 5
6
1 1 4 2
2 3 6
1 1 4 2
1 1 5 2
2 5 10
1 1 5 2


Output

NO
YES
NO
YES

Note

In the first sample, the array initially is {2, 6, 3}. 

For query 1, the first two numbers already have their gcd as 2.

For query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array. 

After query 3, the array is now {9, 6, 3}.

For query 4, no matter which element you change, you cannot get the gcd of the range to be 2. 
import java.util.*;
import java.io.*;
import java.lang.Math.*;

public class MainA {

	public static int mod = 20000;
	public static long[] val;
	public static long[] arr;
	static int max = (int) 1e9 + 7;
	//static int cnt=0;
	public static void main(String[] args) {

		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n=in.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextInt();
		}
		SegmentTree sg=new SegmentTree( a, n);
		int q=in.nextInt();
		while(q-->0)
		{
			int t=in.nextInt();
			if(t==1)
			{
				int l=in.nextInt()-1;
				int r=in.nextInt()-1;
				int x=in.nextInt();
				
				int re=sg.getSum(n,l,r,x);
				if(re>1)out.println("NO");
				else out.println("YES");
			}
			else
			{
				int x=in.nextInt()-1;
				int y=in.nextInt();
				sg.updateValue(a, n, x,y);
			}
		}
		out.close();
	}

	static class SegmentTree 
	{
	    int st[]; // The array that stores segment tree nodes
	 
	    /* Constructor to construct segment tree from given array. This
	       constructor  allocates memory for segment tree and calls
	       constructSTUtil() to  fill the allocated memory */
	    SegmentTree(int arr[], int n)
	    {
	        // Allocate memory for segment tree
	        //Height of segment tree
	        int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
	 
	        //Maximum size of segment tree
	        int max_size = 2 * (int) Math.pow(2, x) - 1;
	 
	        st = new int[max_size]; // Memory allocation
	 
	        constructSTUtil(arr, 0, n - 1, 0);
	    }
	 
	    // A utility function to get the middle index from corner indexes.
	    int getMid(int s, int e) {
	        return s + (e - s) / 2;
	    }
	 
	    /*  A recursive function to get the sum of values in given range
	        of the array.  The following are parameters for this function.
	 
	      st    --> Pointer to segment tree
	      si    --> Index of current node in the segment tree. Initially
	                0 is passed as root is always at index 0
	      ss & se  --> Starting and ending indexes of the segment represented
	                    by current node, i.e., st[si]
	      qs & qe  --> Starting and ending indexes of query range */
	    int getSumUtil(int ss, int se, int qs, int qe, int si,int x)
	    {
	        // If segment of this node is a part of given range, then return
	        // the sum of the segment
	        if (qs <= ss && qe >= se)
	            {
	        		//if(st[si]%x!=0)cnt++;return st[si];
	        		if(st[si]%x!=0)
	        		{
	        			if(ss==se)
	        			{
	        				return 1;
	        			}
	        			else
	        			{
	        				int mid = ((ss+se)>>1);
	        				if (st[2*si+1]%x==0)
							{
								//tr("1");
								return getSumUtil(mid + 1, se, qs, qe, 2 * si + 2,x);
							}
							else if (st[2*si+2]%x==0)
							{
								//tr("2");
								return getSumUtil(ss, mid, qs, qe, 2 * si + 1,x);
							}
							else
							{
								//tr("3");
								return 2;
							}
	        			}
	        		}
	        		else
	        		{
	        			return 0;
	        		}
	            }
	 
	        // If segment of this node is outside the given range
	        if (se < qs || ss > qe)
	            return 0;
	 
	        // If a part of this segment overlaps with the given range
	        int mid = getMid(ss, se);
	        return (getSumUtil(ss, mid, qs, qe, 2 * si + 1,x)+
	                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2,x));
	    }
	 
	    /* A recursive function to update the nodes which have the given 
	       index in their range. The following are parameters
	        st, si, ss and se are same as getSumUtil()
	        i    --> index of the element to be updated. This index is in
	                 input array.
	       diff --> Value to be added to all nodes which have i in range */
	    int updateValueUtil(int ss, int se, int i, int nv, int si)
	    {
	        // Base Case: If the input index lies outside the range of 
	        // this segment
	        if (i < ss || i > se)
	            return st[si];
	 
	        // If the input index is in range of this node, then update the
	        // value of the node and its children
	        
	        if (se == ss) {
	           st[si]=nv;
	           return st[si];
	        }
	        else
	        {
	        	int mid = getMid(ss, se);
		           st[si]=gcd( updateValueUtil(ss, mid, i, nv, 2 * si + 1),
		            updateValueUtil(mid + 1, se, i, nv, 2 * si + 2));
		           return st[si];
	        }
	    }
	 
	    // The function to update a value in input array and segment tree.
	   // It uses updateValueUtil() to update the value in segment tree
	    void updateValue(int arr[], int n, int i, int new_val)
	    {
	        // Check for erroneous input index
	        if (i < 0 || i > n - 1) {
	            System.out.println("Invalid Input");
	            return;
	        }
	 
	        
	        arr[i] = new_val;
	 
	        // Update the values of nodes in segment tree
	        updateValueUtil(0, n - 1, i, new_val, 0);
	    }
	 
	    // Return sum of elements in range from index qs (quey start) to
	   // qe (query end).  It mainly uses getSumUtil()
	    int getSum(int n, int qs, int qe,int x)
	    {
	        // Check for erroneous input values
	        if (qs < 0 || qe > n - 1 || qs > qe) {
	            System.out.println("Invalid Input");
	            return -1;
	        }
	        return getSumUtil(0, n - 1, qs, qe, 0,x);
	    }
	 
	    // A recursive function that constructs Segment Tree for array[ss..se].
	    // si is index of current node in segment tree st
	    int constructSTUtil(int arr[], int ss, int se, int si)
	    {
	        // If there is one element in array, store it in current node of
	        // segment tree and return
	        if (ss == se) {
	            st[si] = arr[ss];
	            return arr[ss];
	        }
	 
	        // If there are more than one elements, then recur for left and
	        // right subtrees and store the sum of values in this node
	        int mid = getMid(ss, se);
	        st[si] = gcd(constructSTUtil(arr, ss, mid, si * 2 + 1) ,
	                 constructSTUtil(arr, mid + 1, se, si * 2 + 2));
	        return st[si];
	    }
	 
	    
	}
	static class Pairs implements Comparable<Pairs> {
		long x;
		int y;

		Pairs(long a, int b) {
			x = a;
			y = b;
		}

		@Override
		public int compareTo(Pairs o) {
			// TODO Auto-generated method stub
			if (x == o.x)
				return Integer.compare(y, o.y);
			else
				return Long.compare(x, o.x);
		}

	}

	

	public static int gcd(int x, int y) {
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}


	public static long pow(long n, long p) {
		long result = 1;
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		while (p != 0) {
			if (p % 2 == 1)
				result *= n;
			p >>= 1;
			n *= n;
		}
		return result;
	}

	static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] nextLongArray(int n) {
			long a[] = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public String readString() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}

 

