# A Kth Root Subarray SOLUTION September Circuits ’20

Page Contents

### A Kth Root Subarray

The difficult proclamation is basic.

You are given a cluster An of N numbers. You need to answer Q questions of three sorts.

1 L R : Determine if the subarray [ AL , AL+1 , AL+2 , ….. AR ] is exceptional or not.

2 L R X Y : Multiply all the components of the subarray [ AL , AL+1 , AL+2 , ….. AR ] by XY.

3 L R X : Reset all the components of the subarray [ AL , AL+1 , AL+2 , ….. AR ] to esteem X.

Let = Product of the subarray [ AL , AL+1 , AL+2 , ….. AR ]

A subarray is exceptional if is a number . At the end of the day the Kth base of result of the subarray ought to be a number.

Info Format

First line contains three numbers N K Q.

Next line contains N numbers A1 , A2 , A3 , ….. A .

Next Q lines contains one of the three kinds of inquiries.

Imperatives

1 <= N <= 105

1 <= Q <= 5*104 ,

1 <= Ai , X , Y <= 106

1 <= L<=R <= N

1 <= K <= 30000

Yield

For each question of type 1 , print Yes if the subarray is exceptional else No

Test INPUT

11 2 9

2 3

1 10 11

1 4 7

3 5 6 3

1 4 7

2 3 5 3 1

1 3 6

3 5 3

1 3 6

1 2 6

Test OUTPUT

No

Truly

Truly

No

Truly

No

Clarification

Exhibit during first inquiry : A = [ 2 3 ]

A[10] * A[11] = 6 which doesnot have a whole number square root.

Cluster during second question : A = [ 2 3 ]

A[4] * A[5] * A[6] * A[7] = 16 which has a whole number square root = 4

Cluster after third question : A = [ 2 3 2 3 ]

For fourth inquiry :

A[4] * A[5] * A[6] * A[7] = 36 which has a whole number square root = 6

Cluster after fifth question : A = [ 2 6 9 3 2 3 ]

For sixth inquiry :

A[3] * A[4] * A[5] * A[6] = 972 which doesnot have a whole number square root