Background

This problem is the strengthened version. For the weakened version, please refer to $NOIP2017$ $DAY2$ $T3$.

Okay, just to scare you a bit.

Problem Description

Some time ago, $k$-xiao-$l$ joined the military training for Grade 10 at $CTYZ$. As everyone knows, during military training you need to stand in a square formation.

In the team where $k$-xiao-$l$ is, there were originally $2*N$ people (weak ones and top ones), but now only a few top ones including $k$-xiao-$l$ and some weak ones are left.

Top one $dwq$: Instructor, I still haven't finished debugging the last problem of this year's $IOI$. I'll go back first and solve it.

Instructor: OK, leave approved. If you finish debugging in ten minutes, go back and rest first.

Weak one $yz$: Instructor, I haven't finished the hard problems in today's task plan. I want to go back and do them.

Instructor: Even if you go back now you still can't debug it. Stand properly. Stop trying to slack off.

$k$-xiao-$l$ is a boy who loves learning. Now he finds that there are only two columns left on the playground. Originally, both columns had length $N$, but now they are incomplete. The weak ones stand in the first column, and the top ones stand in the second column. Also, if there is a top one in a row, their presence will make the weak ones in the adjacent position not dare to stand there.

Even so, the remaining top ones are still stronger than the weak ones (obviously).

In $CTYZ$, the fighting value of one column is defined as

where $i$ is the row index starting from $0$, and $p_{i}=1/0$ indicates whether there is a person in this row.

Now $k$-xiao-$l$ already knows the current standing situation of the top-one column. He wants to ask you: how many possible standing ways can the weak ones have?

However, $k$-xiao-$l$ thinks this is too easy. He now has $M$ queries. Each query gives you a weak-ones fighting value range $[a,b]$ and a $k$, meaning he wants to know: among the weak-ones standing ways whose fighting value is within $[a,b]$, what is the fighting value of the $k$-th largest one. If the total number of standing ways is less than $k$, then output $POOR$ $AFO!$.

Input Format

The first line contains two integers $N,M$, meaning the queue has $N$ rows, and $k$-xiao-$l$ has $M$ queries.

The second line is a $01$ string, representing the standing way of the top ones.

The next $M$ lines each contain three numbers $a_{i},b_{i},k_{i}$, representing the queries of $k$-xiao-$l$.

Output Format

Output $M$ lines, each being the answer. $k$-xiao-$l$ is very kind and allows you to output the fighting value modulo $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

Hint

For $50\%$ of the data, $N<=20,M<=50$.

For $100\%$ of the data, $N<=62,M<=500000$.

The time limit is very loose, so feel free to enjoy it.

Translated by ChatGPT 5