Elimination Tournament Possibility

In an elimination tournament with \(2^n\) contestants, each contestant has a unique strength equal to his index \(i\) (i.e. contestant \(i\) has strength \(i\)). The tournament is played in \(n\) rounds. In each match, two contestants face each other and the winner advances. However, the outcome of each match is not determined by the usual rule. Instead, every match is played under one of two rules:

• Rule One (denoted by max): the contestant with the higher strength wins.
• Rule Two (denoted by min): the contestant with the lower strength wins.

The complete tournament bracket (i.e. the pairing structure and the rule assigned to every match) is predetermined. However, the assignment of the \(2^n\) contestants to the leaves of the bracket is not fixed; it can be arranged arbitrarily. We say that a contestant "reaches round \(b\)" if by winning matches along some branch (by an appropriate assignment of contestants to the bracket), he can appear in round \(b\). In particular, if a contestant wins the final match (round \(n\)), we say he has reached round \(n+1\) (i.e. he is the champion).

You are given the tournament bracket rules and \(m\) queries. In each query, you are given two integers \(a\) and \(b\). Determine if it is possible to assign contestants to the bracket so that contestant \(a\) (with strength \(a\)) reaches round \(b\).

Match Details:

• If a match is played under rule max then the winner must be the stronger contestant. Hence, if contestant \(a\) is to win such a match, his opponent must have strength less than \(a\).
• If a match is played under rule min then the winner is the one with lower strength. Hence, if contestant \(a\) is to win such a match, his opponent must have strength greater than \(a\).

Assume that on the branch a contestant takes to reach round \(b\), let \(x\) be the number of matches played under rule max and \(y\) be the number under rule min (so \(x+y=b-1\)). Notice that for contestant \(a\) to be able to win:

• There must be at least \(x\) contestants with strength lower than \(a\); i.e. \(a-1 \ge x\).
• There must be at least \(y\) contestants with strength higher than \(a\); i.e. \(2^n - a \ge y\).

Your task is to decide, for each query, whether there exists some branch in the bracket (i.e. a root-to-leaf path) whose sequence of match rules \((r_1, r_2, \dots, r_{b-1})\) satisfies the above conditions.

Note: Round \(1\) is the first round; and if \(b = n+1\) then the contestant must be the champion.

inputFormat

The input begins with two integers \(n\) and \(m\) (\(1 \le n \le 10\), \(m \ge 1\)), where \(2^n\) is the number of contestants.

Then follow \(n\) lines describing the tournament bracket rules. The \(i\)th of these lines contains \(2^{n-i}\) tokens (each token is either max or min) describing the rules of the matches in round \(i\).

Then \(m\) lines follow, each containing two integers \(a\) and \(b\). Each query asks whether contestant \(a\) (with strength \(a\)) can be arranged to reach round \(b\) (with \(1 \le b \le n+1\)).

Note: The seeding (assignment of contestants to the bracket leaves) can be arbitrarily chosen.

outputFormat

For each query, output a line containing Yes if it is possible for contestant \(a\) to reach round \(b\) under some seeding arrangement, or No otherwise.

sample

2 4
max min
max
1 2
1 3
4 3
3 3

Yes
No
Yes
Yes

</p>