//package pawan;
import java.util.*;
import java.io.*;
class mystruct
{
int freq;
int data;
int start;
int end;
}
public class Main
{
public static ArrayList<ArrayList<Integer>>pf=new ArrayList<ArrayList<Integer>>();
public static int[] arr;
public static ArrayList<ArrayList<mystruct>>seg=new ArrayList<ArrayList<mystruct>>();
public static int lowsearch(int low,int high,int no,ArrayList<Integer>list)
{
int mid,j;
if(low>high)
return -1;
else if(list.get(high)<no)
return -1;
else
{
mid=(low+high)/2;
if(list.get(mid)>=no)
{
j=lowsearch(low,mid-1,no,list);
if(j<mid&&j!=-1)
return j;
else
return mid;
}
else
return lowsearch(mid+1,high,no,list);
}
}
public static int highsearch(int low,int high,int no,ArrayList<Integer>list)
{
int mid,j;
if(low>high)
return -1;
else if(list.get(low)>no)
return -1;
else
{
mid=(low+high)/2;
if(list.get(mid)<=no)
{
j=highsearch(mid+1,high,no,list);
if(j>=mid)
return j;
else
return mid;
}
else
return highsearch(low,mid-1,no,list);
}
}
public static void fill(int i,int j,int current,ArrayList<Integer>list,ArrayList<mystruct>ans)
{
int mid;
mystruct node,node1,node2;
if(i==j)
{
node=ans.get(current);
node.data=arr[list.get(i)];
node.freq=1;
node.start=i;
node.end=i;
return;
}
else
{
mid=(i+j)/2;
fill(i,mid,2*current+1,list,ans);
fill(mid+1,j,2*current+2,list,ans);
node=ans.get(current);
node1=ans.get(2*current+1);
node2=ans.get(2*current+2);
if(node1.data>node2.data)
{
node.data=node1.data;
node.freq=node1.freq;
node.start=i;
node.end=j;
}
else if(node1.data<node2.data)
{
node.data=node2.data;
node.freq=node2.freq;
node.start=i;
node.end=j;
}
else if(node1.data==node2.data)
{
node.data=node1.data;
node.freq=node1.freq+node2.freq;
node.start=i;
node.end=j;
}
return ;
}
}
public static void construct(ArrayList<Integer>list,int current)
{
int i,k,p;
double x,y,z;
p=list.size();
x=(double)p;
y=(double)2;
k=(int)z;
y=(double)k;
if(y!=z)
y++;
k
=(int)Math.
pow((double)2,y
+1)-1; ArrayList<mystruct>ans;
ans=seg.get(current);
mystruct node;
for(i=0;i<=k-1;i++)
{
node=new mystruct();
ans.add(node);
}
fill(0,list.size()-1,0,list,ans);
return ;
}
public static mystruct result(int i,int j,int current,int prime)
{
mystruct p,q,r;
q=new mystruct();
int x,y,a,c;
p=seg.get(prime).get(current);
x=p.start;
y=p.end;
if(x>=i&&y<=j)
{
q.data=p.data;
q.freq=p.freq;
return q;
}
else if(x>j||y<i)
{
q.data=-1;
q.freq=0;
return q;
}
else
{
q=result(i,j,2*current+1,prime);
r=result(i,j,2*current+2,prime);
a=q.data;
c=r.data;
if(a>c)
return q;
else if(c>a)
return r;
else if(c==a)
{
q.freq=q.freq+r.freq;
return q;
}
}
return q;
}
public static void main
(String[] args
) {
Integer i,j,k,l,m,n,p,q,a,b,c
; str=buf.readLine();
string=str.split(" ");
str=buf.readLine();
string=str.split(" ");
j=string.length;
arr=new int[j];
for(i=0;i<=j-1;i++)
arr
[i
]=Integer.
parseInt(string
[i
]); //precomputation prime seive
int[] primes=new int[100001];
primes[0]=1;
primes[1]=1;
for(i=2;i<=100000;i++)
{
if(primes[i]==1)
continue;
else
{
for(j=2*i;j<=100000;j+=i)
{
primes[j]=1;
}
}
}
ArrayList<Integer>temp;
for(i=0;i<=100000;i++)
{
temp=new ArrayList<Integer>();
pf.add(temp);
}
//prime factorization of the array
for(i=0;i<=n-1;i++)
{
l=arr[i];
for(k=1;k<=j;k++)
{
if(l%k!=0)
continue;
else
{
p=l/k;
if(p==k)
{
if(primes[p]==0)
pf.get(p).add(i);
}
else
{
if(primes[p]==0)
pf.get(p).add(i);
if(primes[k]==0)
pf.get(k).add(i);
}
}
}
}
//segment tree construction
ArrayList<mystruct>temp1;
for(i=0;i<=100000;i++)
{
temp1=new ArrayList<mystruct>();
seg.add(temp1);
}
for(i=0;i<=100000;i++)
{
if(pf.get(i).size()>0)
construct(pf.get(i),i);
}
ArrayList<Integer>temp2=new ArrayList<Integer>();
mystruct help;
int x,y;
for(i=0;i<=m-1;i++)
{
p=-1;
q=-1;
x=-1;
y=-1;
str=buf.readLine();
string=str.split(" ");
k
=(int)Math.
sqrt((double)a
); for(j=1;j<=k;j++)
{
if((a%j)!=0)
continue;
else
{
l=a/j;
if(l==j)
{
if(primes[l]==0)
temp2.add(l);
}
else
{
if(primes[l]==0)
temp2.add(l);
if(primes[j]==0)
temp2.add(j);
}
}
}
//System.out.println(temp2.size());
for(j=0;j<=temp2.size()-1;j++)
{
l=temp2.get(j);
temp=pf.get(l);
p=lowsearch(0,temp.size()-1,b-1,temp);
q=highsearch(0,temp.size()-1,c-1,temp);
//System.out.println(p+" "+q);
if(p==-1||q==-1)
{
p=-1;
q=-1;
}
else
{
help=result(p,q,0,l);
p=help.data;
q=help.freq;
}
if(p>x)
{
x=p;
y=q;
}
}
temp2.clear();
}
}
}
Ly9wYWNrYWdlIHBhd2FuOwppbXBvcnQgamF2YS51dGlsLio7CmltcG9ydCBqYXZhLmlvLio7CmNsYXNzIG15c3RydWN0CnsKCWludCBmcmVxOwoJaW50IGRhdGE7CglpbnQgc3RhcnQ7CglpbnQgZW5kOwp9CnB1YmxpYyBjbGFzcyBNYWluCnsKCXB1YmxpYyBzdGF0aWMgQXJyYXlMaXN0PEFycmF5TGlzdDxJbnRlZ2VyPj5wZj1uZXcgQXJyYXlMaXN0PEFycmF5TGlzdDxJbnRlZ2VyPj4oKTsKCXB1YmxpYyBzdGF0aWMgaW50W10gYXJyOwoJcHVibGljIHN0YXRpYyBBcnJheUxpc3Q8QXJyYXlMaXN0PG15c3RydWN0Pj5zZWc9bmV3IEFycmF5TGlzdDxBcnJheUxpc3Q8bXlzdHJ1Y3Q+PigpOwoJcHVibGljIHN0YXRpYyBpbnQgbG93c2VhcmNoKGludCBsb3csaW50IGhpZ2gsaW50IG5vLEFycmF5TGlzdDxJbnRlZ2VyPmxpc3QpCgl7CgkJaW50IG1pZCxqOwoJCWlmKGxvdz5oaWdoKQoJCQlyZXR1cm4gLTE7CgkJZWxzZSBpZihsaXN0LmdldChoaWdoKTxubykKCQkJcmV0dXJuIC0xOwoJCWVsc2UKCQl7CgkJCW1pZD0obG93K2hpZ2gpLzI7CgkJCWlmKGxpc3QuZ2V0KG1pZCk+PW5vKQoJCQl7CgkJCQlqPWxvd3NlYXJjaChsb3csbWlkLTEsbm8sbGlzdCk7CgkJCQlpZihqPG1pZCYmaiE9LTEpCgkJCQkJcmV0dXJuIGo7CgkJCQllbHNlCgkJCQkJcmV0dXJuIG1pZDsKCQkJfQoJCQllbHNlCgkJCQlyZXR1cm4gbG93c2VhcmNoKG1pZCsxLGhpZ2gsbm8sbGlzdCk7CgkJfQoJfQoJcHVibGljIHN0YXRpYyBpbnQgaGlnaHNlYXJjaChpbnQgbG93LGludCBoaWdoLGludCBubyxBcnJheUxpc3Q8SW50ZWdlcj5saXN0KQoJewoJCWludCBtaWQsajsKCQlpZihsb3c+aGlnaCkKCQkJcmV0dXJuIC0xOwoJCWVsc2UgaWYobGlzdC5nZXQobG93KT5ubykKCQkJcmV0dXJuIC0xOwoJCWVsc2UKCQl7CgkJCW1pZD0obG93K2hpZ2gpLzI7CgkJCWlmKGxpc3QuZ2V0KG1pZCk8PW5vKQoJCQl7CgkJCQlqPWhpZ2hzZWFyY2gobWlkKzEsaGlnaCxubyxsaXN0KTsKCQkJCWlmKGo+PW1pZCkKCQkJCQlyZXR1cm4gajsKCQkJCWVsc2UKCQkJCQlyZXR1cm4gbWlkOwoJCQl9CgkJCWVsc2UKCQkJCXJldHVybiBoaWdoc2VhcmNoKGxvdyxtaWQtMSxubyxsaXN0KTsKCQl9Cgl9CglwdWJsaWMgc3RhdGljIHZvaWQgZmlsbChpbnQgaSxpbnQgaixpbnQgY3VycmVudCxBcnJheUxpc3Q8SW50ZWdlcj5saXN0LEFycmF5TGlzdDxteXN0cnVjdD5hbnMpCgl7CgkJaW50IG1pZDsKCQlteXN0cnVjdCBub2RlLG5vZGUxLG5vZGUyOwoJCWlmKGk9PWopCgkJewoJCQlub2RlPWFucy5nZXQoY3VycmVudCk7CgkJCW5vZGUuZGF0YT1hcnJbbGlzdC5nZXQoaSldOwoJCQlub2RlLmZyZXE9MTsKCQkJbm9kZS5zdGFydD1pOwoJCQlub2RlLmVuZD1pOwoJCQlyZXR1cm47CgkJfQoJCWVsc2UKCQl7CgkJCW1pZD0oaStqKS8yOwoJCQlmaWxsKGksbWlkLDIqY3VycmVudCsxLGxpc3QsYW5zKTsKCQkJZmlsbChtaWQrMSxqLDIqY3VycmVudCsyLGxpc3QsYW5zKTsKCQkJbm9kZT1hbnMuZ2V0KGN1cnJlbnQpOwoJCQlub2RlMT1hbnMuZ2V0KDIqY3VycmVudCsxKTsKCQkJbm9kZTI9YW5zLmdldCgyKmN1cnJlbnQrMik7CgkJCWlmKG5vZGUxLmRhdGE+bm9kZTIuZGF0YSkKCQkJewoJCQkJbm9kZS5kYXRhPW5vZGUxLmRhdGE7CgkJCQlub2RlLmZyZXE9bm9kZTEuZnJlcTsKCQkJCW5vZGUuc3RhcnQ9aTsKCQkJCW5vZGUuZW5kPWo7CgkJCX0KCQkJZWxzZSBpZihub2RlMS5kYXRhPG5vZGUyLmRhdGEpCgkJCXsKCQkJCW5vZGUuZGF0YT1ub2RlMi5kYXRhOwoJCQkJbm9kZS5mcmVxPW5vZGUyLmZyZXE7CgkJCQlub2RlLnN0YXJ0PWk7CgkJCQlub2RlLmVuZD1qOwoJCQl9CgkJCWVsc2UgaWYobm9kZTEuZGF0YT09bm9kZTIuZGF0YSkKCQkJewoJCQkJbm9kZS5kYXRhPW5vZGUxLmRhdGE7CgkJCQlub2RlLmZyZXE9bm9kZTEuZnJlcStub2RlMi5mcmVxOwoJCQkJbm9kZS5zdGFydD1pOwoJCQkJbm9kZS5lbmQ9ajsKCQkJfQoJCQlyZXR1cm4gIDsKCQl9Cgl9CglwdWJsaWMgc3RhdGljIHZvaWQgY29uc3RydWN0KEFycmF5TGlzdDxJbnRlZ2VyPmxpc3QsaW50IGN1cnJlbnQpCgl7CgkJaW50IGksayxwOwoJCWRvdWJsZSB4LHksejsKCQlwPWxpc3Quc2l6ZSgpOwoJCXg9KGRvdWJsZSlwOwoJCXk9KGRvdWJsZSkyOwoJCXo9TWF0aC5sb2cxMCh4KS9NYXRoLmxvZzEwKHkpOwoJCWs9KGludCl6OwoJCXk9KGRvdWJsZSlrOwoJCWlmKHkhPXopCgkJCXkrKzsKCQlrPShpbnQpTWF0aC5wb3coKGRvdWJsZSkyLHkrMSktMTsKCQlBcnJheUxpc3Q8bXlzdHJ1Y3Q+YW5zOwoJCWFucz1zZWcuZ2V0KGN1cnJlbnQpOwoJCW15c3RydWN0IG5vZGU7CgkJZm9yKGk9MDtpPD1rLTE7aSsrKQoJCXsKCQkJbm9kZT1uZXcgbXlzdHJ1Y3QoKTsKCQkJYW5zLmFkZChub2RlKTsKCQl9CgkJZmlsbCgwLGxpc3Quc2l6ZSgpLTEsMCxsaXN0LGFucyk7CgkJcmV0dXJuIDsKCX0KCXB1YmxpYyBzdGF0aWMgbXlzdHJ1Y3QgcmVzdWx0KGludCBpLGludCBqLGludCBjdXJyZW50LGludCBwcmltZSkKCXsKCQlteXN0cnVjdCBwLHEscjsKCQlxPW5ldyBteXN0cnVjdCgpOwoJCWludCB4LHksYSxjOwoJCXA9c2VnLmdldChwcmltZSkuZ2V0KGN1cnJlbnQpOwoJCXg9cC5zdGFydDsKCQl5PXAuZW5kOwoJCWlmKHg+PWkmJnk8PWopCgkJewoJCQlxLmRhdGE9cC5kYXRhOwoJCQlxLmZyZXE9cC5mcmVxOwoJCQlyZXR1cm4gcTsKCQl9CgkJZWxzZSBpZih4Pmp8fHk8aSkKCQl7CgkJCXEuZGF0YT0tMTsKCQkJcS5mcmVxPTA7CgkJCXJldHVybiBxOwoJCX0KCQllbHNlCgkJewoJCQlxPXJlc3VsdChpLGosMipjdXJyZW50KzEscHJpbWUpOwoJCQlyPXJlc3VsdChpLGosMipjdXJyZW50KzIscHJpbWUpOwoJCQlhPXEuZGF0YTsKCQkJYz1yLmRhdGE7CgkJCWlmKGE+YykKCQkJCXJldHVybiBxOwoJCQllbHNlIGlmKGM+YSkKCQkJCXJldHVybiByOwoJCQllbHNlIGlmKGM9PWEpCgkJCXsKCQkJCXEuZnJlcT1xLmZyZXErci5mcmVxOwoJCQkJcmV0dXJuIHE7CgkJCX0KCQl9CgkJcmV0dXJuIHE7Cgl9CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKQoJdGhyb3dzIElPRXhjZXB0aW9uCgl7CgkJSW50ZWdlciBpLGosayxsLG0sbixwLHEsYSxiLGM7CgkJQnVmZmVyZWRSZWFkZXIgYnVmPW5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CgkJU3RyaW5nIHN0cjsKCQlTdHJpbmdbXSBzdHJpbmc7CgkJc3RyPWJ1Zi5yZWFkTGluZSgpOwoJCXN0cmluZz1zdHIuc3BsaXQoIiAiKTsKCQluPUludGVnZXIucGFyc2VJbnQoc3RyaW5nWzBdKTsKCQltPUludGVnZXIucGFyc2VJbnQoc3RyaW5nWzFdKTsKCQlzdHI9YnVmLnJlYWRMaW5lKCk7CgkJc3RyaW5nPXN0ci5zcGxpdCgiICIpOwoJCWo9c3RyaW5nLmxlbmd0aDsKCQlhcnI9bmV3IGludFtqXTsKCQlmb3IoaT0wO2k8PWotMTtpKyspCgkJCWFycltpXT1JbnRlZ2VyLnBhcnNlSW50KHN0cmluZ1tpXSk7CgkJLy9wcmVjb21wdXRhdGlvbiBwcmltZSBzZWl2ZQoJCWludFtdIHByaW1lcz1uZXcgaW50WzEwMDAwMV07CgkJcHJpbWVzWzBdPTE7CgkJcHJpbWVzWzFdPTE7CgkJZm9yKGk9MjtpPD0xMDAwMDA7aSsrKQoJCXsKCQkJaWYocHJpbWVzW2ldPT0xKQoJCQkJY29udGludWU7CgkJCWVsc2UKCQkJewoJCQkJZm9yKGo9MippO2o8PTEwMDAwMDtqKz1pKQoJCQkJewoJCQkJCXByaW1lc1tqXT0xOwoJCQkJfQoJCQl9CgkJfQoJCUFycmF5TGlzdDxJbnRlZ2VyPnRlbXA7CgkJZm9yKGk9MDtpPD0xMDAwMDA7aSsrKQoJCXsKCQkJdGVtcD1uZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CgkJCXBmLmFkZCh0ZW1wKTsKCQl9CgkJLy9wcmltZSBmYWN0b3JpemF0aW9uIG9mIHRoZSBhcnJheQoJCWZvcihpPTA7aTw9bi0xO2krKykKCQl7CgkJCWw9YXJyW2ldOwoJCQlqPShpbnQpTWF0aC5zcXJ0KGwpOwoJCQlmb3Ioaz0xO2s8PWo7aysrKQoJCQl7CgkJCQlpZihsJWshPTApCgkJCQkJY29udGludWU7CgkJCQllbHNlCgkJCQl7CgkJCQkJcD1sL2s7CgkJCQkJaWYocD09aykKCQkJCQl7CgkJCQkJCWlmKHByaW1lc1twXT09MCkKCQkJCQkJCXBmLmdldChwKS5hZGQoaSk7CgkJCQkJfQoJCQkJCWVsc2UKCQkJCQl7CgkJCQkJCWlmKHByaW1lc1twXT09MCkKCQkJCQkJCXBmLmdldChwKS5hZGQoaSk7CgkJCQkJCWlmKHByaW1lc1trXT09MCkKCQkJCQkJCXBmLmdldChrKS5hZGQoaSk7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJCS8vc2VnbWVudCB0cmVlIGNvbnN0cnVjdGlvbgoJCUFycmF5TGlzdDxteXN0cnVjdD50ZW1wMTsKCQlmb3IoaT0wO2k8PTEwMDAwMDtpKyspCgkJewoJCQl0ZW1wMT1uZXcgQXJyYXlMaXN0PG15c3RydWN0PigpOwoJCQlzZWcuYWRkKHRlbXAxKTsKCQl9CgkJZm9yKGk9MDtpPD0xMDAwMDA7aSsrKQoJCXsKCQkJaWYocGYuZ2V0KGkpLnNpemUoKT4wKQoJCQkJY29uc3RydWN0KHBmLmdldChpKSxpKTsKCQl9CgkJQXJyYXlMaXN0PEludGVnZXI+dGVtcDI9bmV3IEFycmF5TGlzdDxJbnRlZ2VyPigpOwoJCW15c3RydWN0IGhlbHA7CgkJaW50IHgseTsKCQlmb3IoaT0wO2k8PW0tMTtpKyspCgkJewoJCQlwPS0xOwoJCQlxPS0xOwoJCQl4PS0xOwoJCQl5PS0xOwoJCQlzdHI9YnVmLnJlYWRMaW5lKCk7CgkJCXN0cmluZz1zdHIuc3BsaXQoIiAiKTsKCQkJYT1JbnRlZ2VyLnBhcnNlSW50KHN0cmluZ1swXSk7CgkJCWI9SW50ZWdlci5wYXJzZUludChzdHJpbmdbMV0pOwoJCQljPUludGVnZXIucGFyc2VJbnQoc3RyaW5nWzJdKTsKCQkJaz0oaW50KU1hdGguc3FydCgoZG91YmxlKWEpOwoJCQlmb3Ioaj0xO2o8PWs7aisrKQoJCQl7CgkJCQlpZigoYSVqKSE9MCkKCQkJCQljb250aW51ZTsKCQkJCWVsc2UKCQkJCXsKCQkJCQlsPWEvajsKCQkJCQlpZihsPT1qKQoJCQkJCXsKCQkJCQkJaWYocHJpbWVzW2xdPT0wKQoJCQkJCQkJdGVtcDIuYWRkKGwpOwoJCQkJCX0KCQkJCQllbHNlIAoJCQkJCXsKCQkJCQkJaWYocHJpbWVzW2xdPT0wKQoJCQkJCQkJdGVtcDIuYWRkKGwpOwoJCQkJCQlpZihwcmltZXNbal09PTApCgkJCQkJCQl0ZW1wMi5hZGQoaik7CgkJCQkJfQoJCQkJfQoJCQl9CgkJCS8vU3lzdGVtLm91dC5wcmludGxuKHRlbXAyLnNpemUoKSk7CgkJCWZvcihqPTA7ajw9dGVtcDIuc2l6ZSgpLTE7aisrKQoJCQl7CgkJCQlsPXRlbXAyLmdldChqKTsKCQkJCXRlbXA9cGYuZ2V0KGwpOwoJCQkJcD1sb3dzZWFyY2goMCx0ZW1wLnNpemUoKS0xLGItMSx0ZW1wKTsKCQkJCXE9aGlnaHNlYXJjaCgwLHRlbXAuc2l6ZSgpLTEsYy0xLHRlbXApOwoJCQkJLy9TeXN0ZW0ub3V0LnByaW50bG4ocCsiICIrcSk7CgkJCQlpZihwPT0tMXx8cT09LTEpCgkJCQl7CgkJCQkJcD0tMTsKCQkJCQlxPS0xOwoJCQkJfQoJCQkJZWxzZQoJCQkJewoJCQkJCWhlbHA9cmVzdWx0KHAscSwwLGwpOwoJCQkJICAgIHA9aGVscC5kYXRhOwoJCQkJICAgIHE9aGVscC5mcmVxOwoJCQkJfQoJCQkJaWYocD54KQoJCQkJewoJCQkJCXg9cDsKCQkJCQl5PXE7CgkJCQl9CgkJCX0KCQkJdGVtcDIuY2xlYXIoKTsKCQkJU3lzdGVtLm91dC5wcmludGxuKHgrIiAiK3kpOwoJCX0KCX0KfQo=