Prefix Set Merging Value Problem

Little Wei is studying string algorithms and has just begun learning the KMP algorithm. His friend Little Hai, who is an expert in KMP, explains the algorithm and poses the following challenge:

Given a string \( s \) of length \( n \), define for every non‐empty prefix \( s_{1:i} \) a value \[ v_i = i \oplus \operatorname{len}(\operatorname{border}(s_{1:i})) \] where:

• \( \oplus \) denotes the bitwise XOR operation,
• \( \operatorname{border}(s) \) is the longest proper prefix of \( s \) that is also a suffix (for example, \( \operatorname{border}(abcda)=a \) and \( \operatorname{border}(aaa)=aa \)),
• \( \operatorname{len}(s) \) is the length of string \( s \).

By convention, the empty string \( \varepsilon \) has a value \( v_0 = 0 \).

When selecting a prefix \( t \) of \( s \), Little Hai requires that Little Wei also selects the prefix \( \operatorname{border}(t) \) (and recursively, the border of the border, and so on, until the empty string is reached). Thus, the prefix set corresponding to a chosen prefix \( t \) is

[ { t, \operatorname{border}(t), \operatorname{border}(\operatorname{border}(t)), \dots, \varepsilon }. ]

Define the value of a prefix set as the sum of the values of all its elements, where for a nonempty prefix \( s_{1:i} \), its value is \( v_i = i \oplus \operatorname{len}(\operatorname{border}(s_{1:i})) \) and the empty string contributes \(0\).

Now consider the following merging operation on two different prefix sets, say, one corresponding to \( x=s_{1:i} \) and another to \( y=s_{1:j} \):

[ \Big( (u \cup v) \setminus (u \cap v)\Big) \cup {g(x,y)} ]

Here, \( g(x,y) \) is defined as the longest common border of \( x \) and \( y \). In particular, if \( x \) is contained in the prefix set of \( y \), then \( g(x,y)=x \). The merged prefix set's value is the sum of the values of its elements.

For example, if \( u \) is the prefix set of \( aaa \) (namely, \( \{aaa,\, aa,\, a,\, \varepsilon\} \)) and \( v \) is the prefix set of \( aba \), then after merging we have

[ {\varepsilon, a, aa, aaa, aba} \setminus {\varepsilon,a} \cup {a} = {a, aa, aaa, aba}. ]

Little Hai will give Little Wei \( m \) queries. In each query an integer \( k \) is given, and the question is: Is there a pair of different prefix sets (obtained from two different chosen prefixes of \( s \)) such that the value of their merged set equals \( k \)?

Note: Due to the nature of the definition, the only possible prefix sets are those obtained by choosing a prefix \( s_{1:i} \) (\( 1 \le i \le n \)). For each such prefix, define:

[ F(i)= i\oplus \pi(i) \quad \text{and} \quad S(i)=F(i)+S(\pi(i)) ]

where \( \pi(i)=\operatorname{len}(\operatorname{border}(s_{1:i})) \) (with \( \pi(1)=0 \)) and with \( S(0)=0 \). If we view the border relation as a tree, then the chain of borders for a prefix \( s_{1:i} \) is obtained by repeatedly applying \( \pi(\cdot) \). For any two chosen prefixes \( s_{1:i} \) and \( s_{1:j} \), let their longest common border (i.e. the maximum element in the intersection of their border chains) be \( g(s_{1:i},s_{1:j}) \). It turns out that the merged set's value can be computed by the formula:

[ \text{merged}(i,j)=S(i)+S(j)-2S(g) + \Bigl(g \oplus \pi(g)\Bigr) ]

Your task is to process \( m \) queries. For each query, output Yes if there exist two different prefixes \( s_{1:i} \) and \( s_{1:j} \) (with \( i\neq j \)) for which the value of the merged set equals the given integer \( k \); otherwise output No. It is guaranteed that the size of \( s \) is small enough so that a solution with quadratic complexity in \( n \) is acceptable.

inputFormat

The first line contains a non-empty string \( s \) (consisting of lowercase letters only).

The second line contains an integer \( m \) representing the number of queries.

Each of the following \( m \) lines contains an integer \( k \).

\(1 \leq |s| \leq 1000\) and \(1 \leq m \leq 1000\).

outputFormat

For each query, output a single line with either Yes or No indicating whether such a pair of distinct prefix sets exists.

sample

aaa
3
4
5
6

Yes
Yes
No

</p>