there are three question :

1st : Arrays and queries

Given an array A with N integers, perform Q queries.

You are given the following types of queries:

1. L X change the value of AL to X.

2. L R X Find the first index P such that Ap ≤ X and L <= P <= R Print P for this type of query. If there is no such P. print -1.

Note: Assume 1-based indexing.

Function description

Complete the solve function. This function takes the following 4 parameters and returns the array of integers corresponding to the query of type 2:

• N. Represents the number of elements of array A

• A: Represents the integer array of size N

• Q. Represents the number of queries

• Queries: Qarrays, one for each query. Each array contains 3 or 4 integers based on the type of query

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

The first line of input contains a single integer N.
The second line contains N space-separated integers, elements of array A.

The next line contains a single integer Q. denoting the number of queries.

Q lines follow each containing a query as specified in the problem statement.

Output format

Print a single integer for each query of type 2.

Constraints

1 ≤ N ≤2×1e5, 
1 < A, ≤ 1e9 ,
1 ≤ L <= R<= N,
1<Q≤1e6.

Input 
10
12 71 80 22 48 13 75 81 68 52
4
2 1 10 27
1 2 49
1 3 26
2 2 10 7

output :
1
-1

Explanation : In the first query, the element at index 1 is less than x, hence the answer is 1.

2nd : it was dfs/bfs Problem number of island's another version.

3rd :  Divisor queries

Given an array a of N numbers. You have to answer Q queries of the following type:

1. I,r: For each i with l≤ i ≤r, a[i]=a[i]/d, where d is the smallest prime factor of a[i].

2. I,r: Print the sum of all a[i]; with l ≤ i ≤r.

3. i k set a[i] = k.

Function description

Complete the Divisor_Queries function. This function takes the following 4 parameters and returns the answer:

N: Represents an Integer representing the length of the array a

Q: Represents an Integer denoting the number of queries

a. Represents an array of length N denoting array a

•Queries. Represents a 2D array of Q rows and 3 columns representing the three types of queries

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

The first line contains two space-separated integers N and Q.

The next line contains / space separated Integers a

The next Q lines contain three space-separated integers denoting the query type and its parameters.

Output format

Print K lines, where K is equal to the number of queries of type 2, with the corresponding answer.

Constraints

1 ≤ N ≤2 * 1e5

1≤ Q≤ 1e5

1≤ ai, k≤ 1e6

Sample input
5  3
10 2 8 7 6
2 1 4
1 1 4
2 1 4

Sample output
27
11

Explanation

First operation (2 1 4)

Sum = 10 + 2 + 8 + 7 = 27

Second operation (1 1 4)

new array, 5 1 4 1 6

Third operation (2 1 4)

Sum = 5 + 1 + 4 + 1 = 11