题目描述

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

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

比赛的过程是这样的，每个小朋友一次上场，设当前上场的小朋友编号为$j$，他的桶悬挂在空中，设桶的上直径为$a$，下直径为$b$，接着，有$n$个球在桶的上方垂直下落（为了简化问题，我们取桶的垂直截面来代表一个桶）。设当前下落的小球的半径为$r$，自然会出现下述三种情况。

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

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

输入

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

第二行有$n$个整数$r_1,r_2,r_3……r_n(1\leq r_i\leq 10^4)$，表示每个小球的半径。

接下来$q$行，每行有两个整数$a$和$b(1\leq b< a\leq 2\times 10^4)$，表示一个小朋友制作的桶的上下直径。

输出

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

测试样例1

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

2 2 0  
1 3 0  
3 1 0