410629: GYM104067 D Самая страшная история

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

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

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

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

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

• по номеру символа в истории узнать порядковый номер слова и позицию символа в этом слове;
• по номеру слова и позиции символа в нем узнать его номер в истории;
• вставить символ (букву или пробел) в определенную позицию в истории;
• удалить символ на определенной позиции в истории.

Помогите Джеку быстро совершить с историей все операции, чтобы он мог наконец-то рассказать ее друзьям!

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

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

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

В $$$i$$$ из следующих $$$m$$$ строк дано описание $$$i$$$-й операции:

• «?1 i» — найти номер слова и позицию в слове для символа под номером $$$i$$$ ($$$1 \leqslant i \leqslant L$$$, где $$$L$$$ — текущая длина истории);
• «?2 w p» — найти для $$$p$$$-го символа в $$$w$$$-м слове его позицию в истории ($$$1 \leqslant w \leqslant W$$$; $$$1 \leqslant p \leqslant P$$$, где $$$W$$$ — текущее количество слов, а $$$P$$$ — длина $$$w$$$-го слова);
• «+ i c» — вставить символ $$$c$$$ на позицию $$$i$$$ в историю ($$$1 \leqslant i \leqslant L$$$; $$$c$$$ — строчная латинская буква или «_» для пробела);
• «- i» — удалить $$$i$$$-й символ из истории ($$$1 \leqslant i \leqslant L$$$).

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

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

Для каждого запроса первого типа выведите в отдельной строке пару чисел $$$w$$$ и $$$p$$$ — номер слова и позицию символа в нем. Для каждого запроса второго типа, аналогично, выведите в отдельной строке число $$$i$$$ — позицию запрошенного символа в истории.

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

3 16
hell spirits fear
?1 1
?2 3 1
+ 12 _
?2 3 1
+ 13 i
?1 13
?1 14
?1 16
?1 7
- 5
?1 7
?2 1 8
- 1
- 1
?2 2 1
?2 3 2

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

1 1
14
13
3 1
3 2
4 1
2 2
1 7
8
10
14