410622: GYM104066 E Самая страшная история

E. Самая страшная историяограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Маленький Джек решил написать самую страшную историю, чтобы напугать своих друзей на Хэллоуин.

Назовем историей непустую последовательность из слов, разделенных пробелами. Слово в истории — непустая последовательность строчных букв латинского алфавита.

Как известно, на качество истории влияют не только слова, содержащиеся в ней, но и символы, содержащиеся в этих словах.

Джек уже составил историю из $$$n$$$ слов. Теперь он хочет проверить $$$m$$$ гипотез относительно получившейся истории, чтобы убедиться, что она действительно страшная. Для проверки каждой гипотезы ему необходимо по номеру символа в истории узнать порядковый номер слова и позицию символа в этом слове.

Входные данные

В первой строке ввода через пробел даны два числа $$$n$$$ и $$$m$$$ — количество слов в истории и количество гипотез ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 5 \cdot 10^5$$$).

В следующей строке записана история, написанная Джеком — $$$n$$$ слов из строчных латинских букв, разделенные пробелами. Гарантируется, что суммарная длина слов не превышает $$$10^6$$$.

В последней строке ввода через пробел перечислены $$$m$$$ целых чисел — номера символов в гипотезах Джека ($$$1 \leqslant x_i \leqslant \sum\limits_{i=1}^n |s_i|$$$).

Выходные данные

Выведите $$$m$$$ пар чисел, каждую в отдельных строке. Пара чисел в $$$i$$$-й строке — порядковый номер слова, в котором содержится $$$i$$$-й символ, и номер этого символа в слове (слова и символы нумеруются с единицы).

ПримерВходные данные

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