#u1005. 小卉的儿童节

小卉的儿童节

题目描述

很快就是一年一度的儿童节了,为庆祝小朋友们的第33个儿童节,小卉幼儿园举办了“接球大赛”。

众所周知,小卉幼儿园以”趣味校园“为办园宗旨,组委会决定事先不告诉小朋友们球的半径,希望小朋友们可以自己去推测,因此最后的冠军只有比赛结束后才知道。 组委会特别规定,用来接球的桶是一个上直径为aa、下直径bb、高hh的一个类似圆台的东西。为了让更多的球进去,组委会希望小朋友们的桶 h>+h->+∞

比赛的过程是这样的,每个小朋友一次上场,设当前上场的小朋友编号为jj,他的桶悬挂在空中,设桶的上直径为aa,下直径为bb,接着,有nn个球在桶的上方垂直下落(为了简化问题,我们取桶的垂直截面来代表一个桶)。设当前下落的小球的半径为rr,自然会出现下述三种情况。

image

  • 小球进入桶的体积始终严格小于(<)(<)球自身一半时,组委会认为小球未进入桶中(如图1),此时会有工作人员将小球拿走。
  • 小球进入桶中,但经过无穷多的时间后落下,组委会认为小球进入了桶中(如图2),此时的工作人员仍会将小球拿走。
  • 小球进入桶中,但是在无穷多的时间后,小球在桶中的体积严格小于(<)(<)球自身一半时,组委会认为小球进入桶,但最终出去了,此时仍然有工作人员将小球拿走。
  • 特别的,当小球直径恰好等于桶的上下某个直径时,小球会卡在桶上,不会继续下落。

由于组委会忙着准备比赛,想请善于编程的你求一下每个小朋友未进球的数目、进入桶中的数目但最终未从桶中出去、最终从桶中出去的数目。

输入

第一行有两个整数nnqq(2n2×106,1q104)(2\leq n\leq 2 \times 10^6,1\leq q \leq 10^4),分别表示组委会准备的nn个小球,和有qq个小朋友参加了比赛。

第二行有nn个整数r1,r2,r3rn(1ri104)r_1,r_2,r_3……r_n(1\leq r_i\leq 10^4),表示每个小球的半径。

接下来qq行,每行有两个整数aab(1b<a2×104)b(1\leq b< a\leq 2\times 10^4),表示一个小朋友制作的桶的上下直径。

输出

输出共qq行,每一行三个整数,分别表示小球未进桶的数目、进入桶中的数目但最终未从桶中出去、最终从桶中出去的数目,请严格按照顺序输出。

测试样例1

4 3  
2 4 3 1  
4 1  
6 2  
2 1
2 2 0  
1 3 0  
3 1 0