Маленький Коля решил написать интересную рождественскую историю для своих друзей.

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

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

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

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

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

Формат входных данных

В первой строке ввода через пробел даны два числа n и m — количество слов в истории и количество операций (1 ≤ n, m ≤ 2 · 10⁵).

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

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

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

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

Формат выходных данных

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

Пример