Маленький Джек решил написать самую страшную историю, чтобы напугать своих друзей на Хэллоуин.
Назовем историей непустую последовательность из слов, разделенных пробелами. Слово в истории — непустая последовательность строчных букв латинского алфавита.
Как известно, на качество истории влияют не только слова, содержащиеся в ней, но и символы, содержащиеся в этих словах.
Джек уже составил историю из $$$n$$$ слов. Теперь он хочет совершить с этой историей $$$m$$$ операций, каждая из которых заключается либо в проверке того, насколько история страшная, либо в небольшом изменении этой истории. Формально, Джек может делать с историей четыре вида операций:
Помогите Джеку быстро совершить с историей все операции, чтобы он мог наконец-то рассказать ее друзьям!
В первой строке ввода через пробел даны два числа $$$n$$$ и $$$m$$$ — количество слов в истории и количество операций ($$$1 \leqslant n, m \leqslant 2 \cdot 10^5$$$).
В следующей строке записана история, написанная Джеком — $$$n$$$ слов из строчных латинских букв, разделенные пробелами. Гарантируется, что суммарная длина слов не превышает $$$10^5$$$.
В $$$i$$$ из следующих $$$m$$$ строк дано описание $$$i$$$-й операции:
Гарантируется, что ни в какой момент времени в истории нет двух пробелов подряд и нет пробела в начале, и что символы в запросах первого типа — всегда буквы, а не пробелы.
Для каждого запроса первого типа выведите в отдельной строке пару чисел $$$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