Substring

Recently, an encrypted message, represented by the string (s), was intercepted. All resources at the analytical center where you work are now focused on decoding it.

Your department specializes in next-generation ciphers. Currently, there are (n) known ciphers, each defined by three parameters: integers (l), (r), and a string (t). If a string (g) results from applying one of these ciphers, then the substring (g_lg_l+1...g_r-1g_r) (where (g_i) is the (i)-th character of (g)) must contain (t) as a substring.

Your task is to determine for each encryption type whether the message (s) could have been produced by applying that encryption method.

Input

The first line of the input contains the string (s) ((1 $\le$ |s| $\le$ 100000), where (|s|) is the length of the string (s)).

The second line contains an integer (n), the number of encryption types ((1 $\le$ n $\le$ 100000)). The next (n) lines each contain two integers (l_i), (r_i), and the string (t), separated by spaces, which are the parameters for the (i)-th encryption method ((1 $\le$ l_i $\le$ r_i $\le$ |s|)).

All strings consist of lowercase Latin letters. The total length of all (t_i) does not exceed 100000.

Output

Output a single line containing "+" for each encryption type if the message (s) could have been obtained by applying that encryption, or "-" otherwise.

Examples