The problem statement is simple.

You are given an array A of N integers. You have to answer Q queries of three types.

• 1 L R            :   Determine if the subarray [ A_L , A_L+1 , A_L+2 , .....   A_R ] is special or not. 
• 2 L R X Y     :    Multiply all the elements of the subarray  [ A_L , A_L+1 , A_L+2 , .....   A_R ] by X^Y.
• 3 L R X        :    Reset all the elements of the subarray [ A_L , A_L+1 , A_L+2 , .....   A_R ] to value X.

Let \(val=\prod_{i=L}^R A_i\) = Product of the subarray [ A_L , A_L+1 , A_L+2 , .....   A_R ]

A subarray is special if \(\sqrt[K]{val}\)  is a integer . In other words the K^th root of product of the subarray should be a integer.

Input Format

First line contains three integers N K Q.

Next line contains N integers A₁ , A₂ , A₃ , .....   A_N .

Next Q lines contains one of the three types of queries.

Constraints

• 1 <=  N <= 10⁵
• 1 <= Q <= 5*10⁴ ,
• 1 <= A_i , X , Y <= 10⁶
• 1 <= L<=R <= N
• 1 <= K <= 30000

Output

For each query of type 1 , print Yes if the subarray is special else No