Substring#1495
Recently, an encrypted message, represented by the string , 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 known ciphers, each defined by three parameters: integers , , and a string . If a string results from applying one of these ciphers, then the substring g_lg_{l+1}\ldots g_{r-1}g_r (where g_i is the -th character of ) must contain as a substring.
The first line contains the string (1 \leq |s| \leq 100000, where is the length of the string ).
The second line contains an integer , the number of encryption types (1 \leq n \leq 100000). The next lines each contain two integers l_i, r_i, and the string , separated by spaces, which are the parameters for the -th encryption method (1 \leq l_i \leq r_i \leq |s|).
All strings consist of lowercase Latin letters. The total length of all t_i does not exceed .
Output a single line containing "+" for each encryption type if the message could have been obtained by applying that encryption, or "-" otherwise.
Example 1