1678 - A Sequence

Time Limit: 1s Memory Limit: 512MB

Submissions: 49 Solved: 8
Description

Pyy is an engineer in Minieye Company in Statistical Analysis Department. To realize some crucial functions in a statistic analysis system, his boss gives him a job. Pyy is given a sequence A[1], A[2], , A[N], and some operations:

  Operation 0: given two numbers l, r, output the maximum number among A[l], A[l+1], , A[r].

  Operation 1: given three numbers l, r, k, divide A[l], A[l+1], , A[r] by k.

  Pyy feel difficulty doing this job, so he turns to you, a friend with excellent skills in algorithm to help him. Can you solve this problem?

Input

There are multiple cases of data.For each case,

Line 1: N, the number of elements of the sequence.

Line 2: A[1], A[2], ... , A[N].

Line 3: M, the number of operations.

Line 4 ... Line M+3: For each line, 

“0 l r”, representing a query operation, or

“1 l r k” , representing a divide operation.

 

 

1 <= l <= r <= N <= 10^5, 0 <= A[i] <= 10^18, 0 <= M <= 10^5, 1 <= k <= 10^18.

Output

For each query operation, output the maximum number.

 

Sample Input
5
1 2 3 4 5
3
0 1 5
1 3 5 2
0 1 5
Sample Output
5
2
Hint
Source