만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가장 무서운 이야기 (Basic)

면접 대비

시간 제한1초메모리 제한1024 MB

요약
단어 n개로 이루어진 이야기에서 m개의 전체 문자 위치마다 해당 문자가 속한 단어 번호와 단어 안에서의 위치를 구합니다.
난이도

쉬움10점 중 3점

유형
누적 합, 이분 탐색
정답자
아직 제출이 없습니다

문제

작은 잭은 할로윈에 친구들을 겁주려고 가장 무서운 이야기를 쓰고 싶어 한다.

이야기는 공백으로 구분된 단어들의 비어 있지 않은 나열이다. 단어는 라틴 소문자로만 이루어진 비어 있지 않은 문자열이다.

이야기의 품질은 그 안에 있는 단어뿐 아니라 단어를 이루는 문자에도 영향을 받는다.

잭은 이미 nn개의 단어로 이루어진 이야기를 썼다. 이제 그는 완성된 이야기가 정말 무서운지 확인하려고 mm개의 가설을 검증하고자 한다. 각 가설마다 이야기 안에서 문자의 번호가 주어지면, 그 문자가 속한 단어의 번호와 단어 안에서 그 문자의 위치를 구해야 한다.

입력

첫 줄에는 공백으로 구분된 두 정수 nn과 mm이 주어진다. 각각 이야기의 단어 수와 가설의 수이다 (1≤n≤1051 \leq n \leq 10^5; 1≤m≤5×1051 \leq m \leq 5 \times 10^5).

다음 줄에는 잭이 쓴 이야기가 주어진다. 공백으로 구분된 nn개의 단어이며, 단어는 라틴 소문자로만 이루어진다. 모든 단어 길이의 합은 10610^6을 넘지 않는다.

마지막 줄에는 공백으로 구분된 mm개의 정수 xix_i가 주어진다. 가설에서 쓰이는 문자의 번호이다 (1≤xi≤∑i=1n∣si∣1 \leq x_i \leq \sum_{i=1}^n |s_i|).

출력

mm개의 쌍을 각 줄에 하나씩 출력한다. ii번째 줄에는 ii번째 문자가 속한 단어의 번호와 그 문자의 단어 안에서의 번호를 출력한다. 단어와 문자는 1부터 번호를 매긴다.

예제1

  1. 예제 1

    입력
    3 15
    hell spirits fear
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
    예상 출력
    1 1
    1 2
    1 3
    1 4
    2 1
    2 2
    2 3
    2 4
    2 5
    2 6
    2 7
    3 1
    3 2
    3 3
    3 4