Дистанционный практикум по программированию

Consider a sequence of N interegs x_i. In order to run a number-theoretic statistical experiment, a random set of queries to this sequence is generated.

Each query is a pair of integers <r, q>. The result of a query will be the Greatest Common Divisor of the members (GCD) in the subsequence starting with x_r and ending with x_q.

For example, if sequence (1, 2, 4, 6, 12) is given then for query <1, 5> the result equals to GCD(1, 2, 4, 6, 12) = 1, for query <2, 4> the result will be GCD(2, 4, 6) = 2, and for query <4, 5> the result will be GCD(6, 12) = 6.

Your task is to write a program, which will construct a set of results, given a number sequence (x_i) and a set of queries.

Note that the queries may be repeated.

Исходные данные

The first line of the input file contains two integers (N, M) separated by one or several spaces. Number N is the number of elements in the sequence of numbers. (1<N<=10000). Number M is the number of queries (0<M<=100000).

The second line contains N integers x_i that form the sequence. The numbers are delimited by one or more spaces (0<x_i<=10⁹).

Then M lines follow, containing number pairs (r_i, q_i) each. The numbers in a pair are delimited by one or more spaces. A pair is a query for GCD computation of the members x_ri ... x_qi (0<r_i,q_i<=N, r_i<q_i).

Результат

The first line of the output file must contain the number M. The following M lines must contain the answers. The i-th line of those M lines must contain the answer to the query <r_i, q_i>.

Примеры