Binary Expression Evaluation with Custom Operation Table

You are given an operation table \(s\) and \(q\) binary strings. Each binary string has a length of \(2n+1\), where \(n\) is a positive integer. Each such string represents a boolean expression written in the following form:

\(a_0\, op_0\, a_1\, op_1\, a_2\, op_2\, \dots \ op_{n-1}\, a_n\)

Here, the digits at the even positions (0-indexed) are operands (either 0 or 1) and the digits at the odd positions are operators (each operator is either 0 or 1). The operation table \(s\) is a string of 8 characters (each one \(0\) or \(1\)), and it defines a function \(f(a,op,b)\) as follows:

\[ f(a,op,b)= s_{(4a+2op+b)} \quad (0 \le 4a+2op+b \le 7), \]

You are allowed to perform exactly \(n\) operations. In each operation, you choose three consecutive digits (which must be in the pattern operand operator operand) and replace them with a single digit computed by \(f(a,op,b)\). This reduces the length of the string by 2. After exactly \(n\) operations, the string will reduce to a single digit. Your task is to determine, for each given binary string, whether there exists a valid sequence of \(n\) operations that results in the final value \(1\). If such a sequence exists, output 1; otherwise, output 0.

inputFormat

The first line of the input contains the operation table \(s\), a string of exactly 8 characters (each is either 0 or 1).
The second line contains an integer \(q\) representing the number of queries. Each of the following \(q\) lines contains a binary string of length \(2n+1\) (with \(n \ge 1\)).

outputFormat

For each query, output a single line containing 1 if it is possible to obtain the value 1 via exactly \(n\) operations, or 0 otherwise.

sample

01011110
4
101
010
111
10111

1
0
0
1