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