解题思路

1. 先用哈希表统计数组每个值出现次数 freq[v]（数组已排序但不影响，用哈希更快）。

2. 对每个询问：

   • 若 (x=0)：(0^K=0)（(K>=1)），所以只可能是 (a=y) 总数=峰值=freq[y]
   • 若 (x=1)：(1^K=1)，所以只可能是 (a=y+1) 总数=峰值=freq[y+1]
   • 若 (x>=2)：(x^K) 严格递增，只需枚举 (K=1,2,3......)，不断乘 (x) 得到幂 p：

题目内容

服务器常用指数退避策略来避免网络拥塞，每次访问失败后，会大间隔间隔成倍后再访问，下次重试的间隔在最大间隔内随机化。小华作为测试人员模拟了一些输入，服务器后台可看到$n$个访问时间点，第$i$个为$a[i]$(其中$a[i]$值可能重复)。现在他想知道对于一个数对$(x[j],y[j])$，满足$a[i] = (x[j])^K + y[j]$的访问一共有多少个，峰值是多少?

注:$K$看可取任意正整数，峰值指K取某一整数时满足$a[i] =(x[j])^K+y[j]$的数量的最大访问个数。

输入描述

第$1$行两个整数$n,m$，用空格隔开。表示有$n$个数，$m$次询问$(1<=n<=100000,1 <= m <=200000)$。

第$2$行有$n$个数，用空格隔开，第$i$个数为$a[i] (1<=i <= n,1 <= a[i] <=1000000000)$，从小到大排序。

从第$3$行到第$m+2$行，每行两个整数，用空格隔开，表示给定一个整数数对$(x[j],y[j]) (0 <= x[i],y[j] <=10000000)$

输出描述

$m$行，每行两个数，第$j$行回答询问对于$(x[j],y[j])$，可满足$a[i] =(x[j])^K + y[j]$($K$取任意正整数)的数量一共有多少个，峰值为多少，用空格隔开。

样例1

输入

4 2
45 78 90 429981774
12 78 
9 42561285

输出

2 1 
1 1

说明

对于第一组询问,要满足$a[1]=12^K+78$，当$K$取$1.8$时$12^1+78=90=a[3]$，此时刻有1个访问。

$12^8+78=429981774=a[4]$，此时刻有1个访问。因此一共2个，峰值为1。

对于第二组询问,要满足$a[i]=9^K+42561285$，当$K$取$9$时$9^9+42561285 =429981774=a[4]$。因此一共1个，峰值为1。

样例2

输入

11 3
2 3 4 5 5 6 7 7 9 16 17
2 0
2 1
0 7

输出

3 1 
5 2
2 2

说明

对于第一组询问要满足$a[1]=2^K+0$,当$K$取$1,2,4$时:

$2^1+0=2=a[1]$,此时刻有1个访问

$2^2+0=4=a[3]$,此时刻有1个访问

$2^4+0=16=a[10]$,此时刻有1个访问

因此一共$3$个,蜂值为$1$。

对于第二组询问,要满足$a[1]=2^K+1$的$a[1]$,当$K$取1$,2,3,4$时:

$2^1+1=3=a[2]$,此时刻有$1$个访问

$2^2+1=5=a[4]=2[5]$,此时剪有$2$个访问

$2^3+1=9=[9]$,此时充有$1$个访问

$2^4+1=17= a[11]$，此时完有$1$个访问

因此一共$5$个,峰值为$2$

对于第三组询问要满足$a(1)=0^K+7$的a抑,值只能为$7$。$a[7]=a[8]=7$,有两个数满足因此一共$2$个,峰值为$2$