The Scariest Story

Little Jack decided to write the scariest story he could to frighten his friends on Halloween.

A story is a non-empty sequence of words separated by spaces. A word is a non-empty sequence of lowercase Latin letters.

The quality of a story depends on its words and also on the characters inside those words.

Jack has already written a story with $n$ words. Now he wants to perform $m$ operations on it. Each operation either checks how scary the story is or changes it slightly. There are four kinds of operations:

• ?1 i: find the word number and the position inside that word for the character at position $i$ of the story.
• ?2 w p: find the position in the story of the $p$-th character of the $w$-th word.
• + i c: insert character $c$ (a lowercase letter or a space written as \_) at position $i$ of the story.
• - i: delete the character at position $i$ of the story.

The first line contains two integers $n$ and $m$ separated by a space ($1 \leqslant n, m \leqslant 2 \cdot 10^5$).

The second line contains the story: $n$ words separated by spaces. The total length of all words does not exceed $10^5$.

Each of the next $m$ lines describes one operation.

• ?1 i: $1 \leqslant i \leqslant L$, where $L$ is the current length of the story.
• ?2 w p: $1 \leqslant w \leqslant W$ and $1 \leqslant p \leqslant P$, where $W$ is the current number of words and $P$ is the length of the $w$-th word.
• + i c: $1 \leqslant i \leqslant L$. $c$ is a lowercase letter or a space (\_).
• - i: $1 \leqslant i \leqslant L$.

At no moment does the story contain two consecutive spaces or a space at the start. Characters in queries of the first type are always letters, not spaces.

For each query of the first type, print the word number and the position inside the word on one line, separated by a space.

For each query of the second type, print the position in the story on its own line.