列队
题目背景
本题是数据加强版,弱化版请参考$NOIP2017$ $DAY2$ $T3$
~~好了吓吓你们~~
题目描述
前段时间,$k$小$l$参加了$CTYZ$高一的的军训。众所周知,军训的时候需要站方阵。
$k$小$l$ 所在的队伍中有原本有蒟蒻(巨佬)$2*N$个,然而现在的只剩$k$小$l$等少数巨佬和一些蒟蒻了。
巨佬 $dwq$ :教官我还有今年$IOI$的最后一题没调完,我先回去把题切了。
教官:行,准假,过十分钟调完了就先回去休息吧。
蒟蒻 $yz$ :教官我今天任务计划里的红题还没做完,我要回去做。
教官:你现在回去也调不出来,乖乖站♂好,不要老是想偷懒。
$k$小$l$是一个热爱学习的男♀孩子,现在他发现,操场上只剩两列队了,原本两列的长度都为$N$,并且这两列队还残缺不全,蒟蒻在第一列,巨佬在第二列,并且如果一行中有巨佬,其气场会导致旁边不敢站蒟蒻。
#### 就算是这样,仅存巨佬们的战斗力还是比蒟蒻们的战斗力大(废话)
在$CTYZ$里面,一列队战斗力值是这样定义的
$Fight=\sum_{i=0}^{n-1} p_{i}*2^{i}$
其中$i$为行标号,从$0$开始,$p_{i}=1/0$表示这一行是否有人,
现在$k$小$l$已经知道目前巨佬队伍的站队情况,现在他想问你,蒟蒻们有多少种可能的站队方式。
然而$k$小$l$觉得这样的太简单了,$k$小$l$现在有$M$个询问,每次会给你一个蒟蒻战斗力值范围$[a,b]$和一个$k$,表示他希望知道蒟蒻们的战斗力值在$[a,b]$之间,战斗力值第$k$大的蒟蒻站队方式的战斗力值,如果站队方式总数小于$k$,那么输出$POOR$ $AFO!$。
输入输出格式
输入格式
第一行两个个整数$N,M$表示队列有$N$行,$k$小$l$的询问有$M$次。
第二行为一串$01$串,表示巨佬们的站队方式。
接下来$M$行,每行三个数$a_{i},b_{i},k_{i}$,表示$k$小$l$的询问。
输出格式
输出$M$行表示答案,$k$小$l$特别良心,允许你对于这个战斗力取模$20031102$输出。
输入输出样例
输入样例 #1
5 5
0 1 0 1 0
0 4 5
0 3 4
0 0 1
0 1 2
4 4 1
输出样例 #1
POOR AFO!
POOR AFO!
0
0
4
输入样例 #2
10 5
1 1 0 1 1 0 0 1 0 0
0 56 7
30 126 7
62 116 5
20 100 1
8 108 1
输出样例 #2
POOR AFO!
POOR AFO!
POOR AFO!
100
100
输入样例 #3
5 1
0 0 0 0 1
0 999 1
输出样例 #3
15
说明
对于$50$%的数据,$N<=20,M<=50$
对于$100$%的数据,$N<=62,M<=500000$
时限很松,请放心食用。