28537번 - Самая страшная история 다국어

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

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

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

Джек уже составил историю из $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$ --- позицию запрошенного символа в истории.