CF741E Arpa’s abnormal DNA and Mehrdad’s deep interest

All of us know that girls in Arpa’s land are... ok, you’ve got the idea :D Anyone knows that Arpa isn't a normal man, he is ... well, sorry, I can't explain it more. Mehrdad is interested about the reason, so he asked Sipa, one of the best biology scientists in Arpa's land, for help. Sipa has a DNA editor. Sipa put Arpa under the DNA editor. DNA editor showed Arpa's DNA as a string $ S $ consisting of $ n $ lowercase English letters. Also Sipa has another DNA $ T $ consisting of lowercase English letters that belongs to a normal man. Now there are $ (n+1) $ options to change Arpa's DNA, numbered from $ 0 $ to $ n $ . $ i $ -th of them is to put $ T $ between $ i $ -th and $ (i+1) $ -th characters of $ S $ ( $ 0

The first line contains strings $ S $ , $ T $ and integer $ q $ ( $ 1

Print $ q $ integers. The $ j $ -th of them should be the number $ i $ of the most interesting option among those that satisfy the conditions of the $ j $ -th question. If there is no option $ i $ satisfying the conditions in some question, print -1.

Explanation of first sample case: In the first question Sipa has two options: dabc ( $ i=0 $ ) and abdc ( $ i=2 $ ). The latter (abcd) is better than abdc, so answer is $ 2 $ . In the last question there is no $ i $ such that $ 0