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

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

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

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

Джек уже составил историю из $$$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