A native of Snezhinsk, Danya Bagrov, has already grown up, and it's time to find a job. Of course, Danya wanted to get a job at the factory.
Since most of the factories are located in Chelyabinsk (there are more than 60 of them), Snezhinsk got only one, and, accordingly, the demand for such a desired job is very high in this city, therefore, when applying for a factory in Snezhinsk, all employees must solve the problem in programming.
Danya skipped computer science as a child, so everything is bad with programming. Help Dana solve the problem so that he can get a job at the factory without any problems and live in abundance.
Given two arrays of integers a
1,a
2,...,a
n and b
1,b
2,...,b
n and q queries of two types:
1 r x — need to do a
i = x for all l <= i <= r.
2 l r — find the minimum value
\( {lcm (a_i,b_i)\over gcd(a_i,b_i)}\) over all l <= i <= r.
Input
The first line contains two integers n and q (1 <= n,q <= 5 · 10
4) — the number of numbers in arrays a and b and the number of requests.
The second line contains n integers a
1,a
2,...,a
n (1 <= a
i <= 5 · 10
4).
The third line contains n integers b
1,b
2,...,b
n (1 <= b
i <=5 ·10
4).
This is followed by q lines, the j-th of which starts with an integer t (1 <= t <= 2) and means that the j-th query is of type t.
If t =1, then the rest of the line contains the integers l, r, and x (1 <= l <= r <= n, 1 <= x <= 5·10
4< /sup>). If t =2, then the rest of the string contains the integers l and r (1 <= l <= r <= n).
Imprint
For each query of the second type print the answer to the problem. It is guaranteed that there will be at least one such request.
Examples
| # |
Input |
Output |
| 1 |
10 10
6 10 15 4 9 25 2 3 5 30
1 2 3 4 6 9 12 15 18 30
2 1 10
1 7 10 9
2 5 10
1 1 6 14
2 4 7
2 3 9
1 2 9 30
2 1 4
2 3 7
2 5 10
| 1
2
12
2
10
5
2 |