Problem Background

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

Just scaring you a bit

Problem Description

Recently, $k$小$l$ participated in the military training for freshmen at $CTYZ$. As is well known, during military training, one needs to stand in a square formation.

$k$小$l$'s team originally had $2*N$ students, but now only a few, like $k$小$l$, and some others remain.

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

Instructor: Sure, you're excused. Go back and rest after you're done in ten minutes.

Weak $yz$: Instructor, I haven't finished the red problem in today's task plan. I need to go back and do it.

Instructor: You won't solve it even if you go back now. Stand still, don't always think about slacking off.

$k$小$l$ is a boy♀ who loves learning. He noticed that there are only two rows left on the field. Originally, both rows were of length $N$, but now they are incomplete. The weak are in the first row, and the giants are in the second row. If there is a giant in a row, their aura prevents the weak from standing next to them.

Even so, the remaining giants' combat power is still greater than that of the weak (obviously)

In $CTYZ$, the combat power value of a row is defined as:

$= \sum_{i=0}^{n-1} p_{i}*2^{i}$

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

Now, $k$小$l$ knows the current standing situation of the giants. He wants to know how many possible standing formations the weak can have.

However, $k$小$l$ thinks this is too simple. He now has $M$ queries. Each query will give you a range of weak combat power values $[a, b]$ and a $k$, indicating that he wants to know the $k$-th largest combat power value of the weak within the range $[a, b]$. If the total number of formations is less than $k$, output $POOR$ $AFO!$.

Input Format

The first line contains two integers $N, M$, indicating the number of rows in the formation and the number of queries by $k$小$l$.

The second line is a string of $01$, indicating the standing situation of the giants.

The next $M$ lines, each containing three numbers $a_{i}, b_{i}, k_{i}$, indicating $k$小$l$'s query.

Output Format

Output $M$ lines as the answer. $k$小$l$ is very kind and allows you to output the combat power modulo $20031102$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

POOR AFO!
POOR AFO!
0
0
4

Input Sample #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

Output Sample #2

POOR AFO!
POOR AFO!
POOR AFO!
100
100

Input Sample #3

5 1
0 0 0 0 1
0 999 1

Output Sample #3

15

Notes/Hints

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

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

The time limit is generous, feel free to use it.

见题面 Input 部分

见题面 Output 部分