P5141 Queue Formation

This problem is the strengthened version. For the weakened version, please refer to $NOIP2017$ $DAY2$ $T3$. ~~Okay, just to scare you a bit.~~

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 $$Fight=\sum_{i=0}^{n-1} p_{i}*2^{i}$$ 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!$.

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

For $50\%$ of the data, $N