背景

本题是数据加强版，弱化版请参考 NOIP2017 DAY2 T3。

好了吓吓你们

题目描述

前段时间，k 小 l 参加了 CTYZ 高一的的军训。众所周知，军训的时候需要站方阵。

k 小 l 所在的队伍中有原本有蒟蒻（巨佬）$2\times N$ 个，然而现在的只剩 k 小 l 等少数巨佬和一些蒟蒻了。

巨佬 dwq：教官我还有今年 IOI 的最后一题没调完，我先回去把题切了。

教官：行，准假，过十分钟调完了就先回去休息吧。

蒟蒻 yz：教官我今天任务计划里的红题还没做完，我要回去做。

教官：你现在回去也调不出来，乖乖站♂好，不要老是想偷懒。

k 小 l 是一个热爱学习的男♀孩子，现在他发现，操场上只剩两列队了，原本两列的长度都为 $N$，并且这两列队还残缺不全，蒟蒻在第一列，巨佬在第二列，并且如果一行中有巨佬，其气场会导致旁边不敢站蒟蒻。

就算是这样，仅存巨佬们的战斗力还是比蒟蒻们的战斗力大。（废话）

在 CTYZ 里面，一列队战斗力值是这样定义的

其中 $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\le20,M\le50$。

对于 $100\%$ 的数据，$N\le62,M\le5\times10^5$。

时限很松，请放心食用。