402364: GYM100738 J The craziness of Juvel

The well known artist Juvel has started to compose again, but firstly he started to write down on a paper some words. These words are not randomly chosen, being Juvel’s favorite words. After he finally managed to write down all his favorite words, he started to compose a new song. As the artist does not know how to use the punctuation marks, he decided to line the lyrics, creating a string. He reads the lyrics again and changes some letters in order to acquire the perfect song, because he wants this song to become a hit. As the number of favorite words used increases, the quality of the song rises. Juvel wants to know the number of his favorite words used at the beginning of the song and after every change that has been made.

The first line of the input contains an integer N(1 ≤ N ≤ 100) denoting the number of words from his list and an integer M(1 ≤ M ≤ 100000) denoting the number of changes. On the other N lines there is a string with the words from his list. Every word has a length of at most 100. The words from the list are ordered in the Input.

The next line contains a string with the actual song. The length of the song is at most 100000. The next M lines contain an integer pos and a character c, such that it replays the character from the pos position with c. The string with the song is indexed from 1.

Also keep in mind that: length(word₁) + length(word₂) + … + length(word_n)  - LCP(word₁, word₂) - LCP(word₂, word₃) - … - LCP(word_n - 1, word_n) ≤ 100, where LCP is the longest common prefix.

The output contains M + 1 lines, on each line being the number of favorite words used initially and the number of favorite words used after every change.

3 2
bunaciune
smecherie
valoare
smecheriisibunaciuni
9 e
20 e

0
1
2