小王要考察小明对歌曲的了解，他准备了一个MP3，这个MP3会按照顺序放歌，第i首歌会重复ci次，单次时长为ti秒。然后这个MP3就一直循环播放。
小王会提出m个问题，每次会问从 第一首歌开始播放，那么第t秒在放的歌曲是什么名字？
小明早记住了歌曲的名字以及播放的顺序，他需要你帮忙计算出每次询问的歌曲是第几首，这样他就能给出正确答案。
样例1
4 4
3 4
2 4
3 3
1 4
16 25 24 21
样例2
4 2
2 4
2 3
1 3
1 4
13 4样例1
2
3
3
3
样例2
2
1
对于30% 的数据，满足 1<=n,m<=1000。
对于 100%的数据，满足1<=n,m,ci,ti<=10^5 1<=t<=10^18。