You have caught a spy from enemy country, and you would like to know everything about his job. After thoroughly examining his wallet, you found a piece of paper which contains strange codes. This is the command that the spy received, you think. But you do not know how to decode, so you interrogate the spy, and torture him when he refuses to answer.
Finally he tells you the secret way to decode. There are n operations that he prepared to take. Each operation is associated with two integers l, r and a string p. When the commander wants some operations to take place, he would send a message s to the spy. The spy has to execute the i-th operation if and only if the string sli... sri contains the string pi as a substring.
You also found another piece of paper containing li, ri and pi for all i. Please figure out which operations the spy was asked to execute.
The first line of the input file contains an integer T (T<=50), the number of test cases.
Each test case starts with a line containing the string s (1<=|s|<=100000). The second line contains an integer n (1<= n<=100000). Each of the next n lines consists of two integers li, ri and a string pi (1<= li<= ri<=|s|, |p1|+...+|pn|<=100000).
All strings consist of lowercase letters only.
For each test case, please output one line containing n characters. The i-th character is '+' if the spy was asked to execute the i-th operation, or '-' otherwise.
2 frommarsiam 3 6 10 i 2 11 am 1 9 human babaa 5 1 1 a 2 2 a 3 3 a 4 4 a 5 5 a
++- -+-++
Migrated from old NTUJ.
St. Petersburg Olympiad team programming 2010
| No. | Testdata Range | Score |
|---|