Time Limit: 1s
Memory Limit: 512MB
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?
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.
For each query operation, output the maximum number.
5 1 2 3 4 5 3 0 1 5 1 3 5 2 0 1 5
5 2