题目背景

本题是数据加强版，弱化版请参考$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$输出。

5 5
0 1 0 1 0 
0 4 5
0 3 4
0 0 1
0 1 2
4 4 1

POOR AFO!
POOR AFO!
0
0
4

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

POOR AFO!
POOR AFO!
POOR AFO!
100
100

5 1
0 0 0 0 1
0 999 1

15

提示

对于$50$%的数据，$N<=20,M<=50$

对于$100$%的数据，$N<=62,M<=500000$

时限很松，请放心食用。