CF589C Polycarp's Masterpiece

Inspired by success of Joanne Rowling and her fantasy series of Harry Potter, Polycarp decided to create his own masterpiece. He has already picked a name for his future bestseller — string $ s $ . Polycarp faced a number of difficulties while he was working on the main story of his book so he decided to become Malevich in a literature and create his own "Black Square". Chapters of his masterpiece were written by Polycarp in $ n $ days. He started from writing down the string $ s $ . Every day (during the following $ n $ days) he did the following procedure: on the $ i $ -th day he added to the right of current text $ t $ its $ k_{i} $ -th circular shift. It means that every day content of his masterpiece doubled in size. Circular shift of a string $ r $ is defined as a string resulted after movement of the last character of $ r $ to the first position in the string. As an example: circular shift of «masterpiece» is «emasterpiec». The $ i $ -th circular shift of a string $ r $ is defined as a string resulted after applying $ i $ subsequent circular shifts of the string $ r $ (e.g., the third circular shift of «masterpiece» is «ecemasterpi»). After $ n $ days of tedious work Polycarp managed to write a very long text deserving the efforts made. However, text of his masterpiece was so long that it was nearly impossible to do any analysis of its content. Help Polycarp to answer $ m $ requests about his masterpiece: for the $ j $ -th request you will need to find how many times a letter $ c_{j} $ is contained in a substring of his masterpiece starting from position $ l_{j} $ and ending at $ r_{j} $ inclusively.

The first line contains a name of the masterpiece — string $ s $ . The string $ s $ contains only lowercase latin letters and its length is between 1 and 100 inclusively. The second line contains a pair of integer numbers $ n $ and $ m $ $ (1

Output should contain $ m $ lines, where the $ j $ -th line contains the answer on the $ j $ -th request.