접미사 오토마톤
시간 제한6초메모리 제한1024 MB
문자열 S의 서로 다른 부분 문자열을 길이순, 같은 길이면 사전순으로 정렬했을 때 k번째 문자열의 첫 등장 위치 l, r을 구합니다.
문제
JB는 Suffix Automaton의 국가 올림피아드 튜터이다. 오늘 그는 다음 문제를 만들었다.
문자열 가 주어졌다고 하자. 의 서로 다른 부분 문자열을 모두 적는다. 길이가 짧은 순서대로 정렬하고, 길이가 같으면 사전순으로 앞선 문자열을 먼저 둔다. 이렇게 정렬된 문자열의 수열을 라고 한다.
JB는 개의 질문을 준비했다. 각 질문마다 정수 가 주어지면, 에서 번째 문자열을 찾아야 한다.
문제를 단순하게 하려고, 그 문자열이 에서 처음 나타나는 왼쪽 위치와 오른쪽 위치만 출력하면 된다.
입력
첫째 줄에 문자열 가 주어진다(). 는 소문자로만 이루어진다.
둘째 줄에 정수 가 주어진다().
이어지는 개의 줄에 각각 정수 가 하나씩 주어진다().
출력
각 질문에 대해, 답 문자열이 에서 처음 나타나는 왼쪽 위치 과 오른쪽 위치 을 공백으로 구분해 출력한다. 가 의 길이보다 크면 "-1 -1"을 출력한다.