Recently while designing backdoor, vampire got frustrated and went on a mission to â€œNetworking Landâ€ to find peace. There, he came across a number of islands arranged in a row.Each island had a holy number associated with it.The holy number of a range of consecutive islands was the maximum number that could be divided by the holy numbers of all of the islands in that range. Vampire has a number of queries where he needs to find the holy number of some range of islands. Help him do so.
Input The first line contains n (n<=10^5) and q (q<=10^4), the number of islands and the number of queries. the next line contains n integers (every integer is <= 10^9) denoting the holy number of all the islands. this is followed by q lines, each line contains 2 integers l,r.You need to output the holy value of the range l,r.
Output The output should contain q lines, each denoting the answer to each querry