====== 문자열과 쿼리 ======

===== 풀이 =====
  * F(i)의 정의를 살펴보면, 결국 S를 뒤집어서 만든 문자열 S[::-1]에 대해 z배열을 만든것과 동일하다.
  * z배열을 O(n)에 구하면 모든 쿼리를 O(1)에 대답 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13713. 문자열과 쿼리".

- Problem link: https://www.acmicpc.net/problem/13713
- Solution link: http://www.teferi.net/ps/problems/boj/13713

Tags: [Z algorithm]
"""

import sys
from teflib import string as tstring


def main():
    S = sys.stdin.readline().rstrip()
    z_arr = tstring.z_array(S[::-1])

    M = int(sys.stdin.readline())
    for _ in range(M):
        i = int(sys.stdin.readline())
        print(z_arr[-i])


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:string#z-array|teflib.string:z-array]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}