Giant and Jelly Team Arrangement

During the CTYZ high school military training, the two lines of troops have become sparse. One line is for the Jelly (蒟蒻) and the other for the Giants (巨佬). Originally both columns had exactly N positions (rows) indexed from 0 to N-1. However, due to the chaos, some positions are missing. It is known that the Giant column's arrangement is fixed and given as a binary string of length N. In this string, a character '1' indicates that row i is occupied by a Giant, while '0' means that row is empty. The Jelly can only stand in rows where there is no Giant. Moreover, because of the intimidating aura of a Giant, if a Giant occupies row i in the second column, then the Jelly cannot stand in row i of the first column.

Each team’s fighting power is defined by the formula:

\( Fight = \sum_{i=0}^{N-1} p_i \cdot 2^{i} \)

where \( p_i \) is either 1 or 0 indicating whether someone stands in row \( i \) (if the team uses that row). Note that every valid Jelly arrangement corresponds to choosing a subset of rows (among those not blocked by a Giant) where a Jelly will stand, and the fight power is the sum of \(2^i\) for those rows. All such arrangements produce distinct fighting power values.

Now, you are given M queries. In each query, you are provided with a fighting power range \([a, b]\) and a number k. Your task is to determine the k-th largest (in descending order) Jelly arrangement fighting power that lies within the interval \([a, b]\). If there are fewer than k valid arrangements in this interval, output POOR AFO!.

Input/Output specification details are given below.

inputFormat

The input consists of:

• The first line contains two integers \(N\) and \(M\) where \(N\) is the total number of rows and \(M\) is the number of queries.
• The second line contains a binary string of length \(N\) representing the Giant column. The \(i\)-th character is '1' if row \(i\) is occupied by a Giant and '0' otherwise.
• The next \(M\) lines each contain three space-separated integers: \(a\), \(b\), and \(k\) representing a query. \(a\) and \(b\) define the inclusive range of valid fighting power values, and \(k\) denotes that you should output the k-th largest valid fighting power from those within the interval.

You may assume that all input values are valid and that \(0 \leq a \leq b\).

outputFormat

For each query, output one line containing the answer. If there are fewer than \(k\) valid Jelly arrangements whose fighting power lies in \([a, b]\), output POOR AFO! (without quotes). Otherwise, output the fighting power value of the k-th largest arrangement.

sample

3 2
010
0 5 2
1 5 3

4
1