Christmas queries
Tag(s):

## Algorithms, Hard, String Algorithms

Problem
Editorial
Analytics

Little Santa has a list S of names of N nice children and another list P of names of M naughty children. He doesn't want the names of nice children to get mixed with the naughty ones. Little Santa himself is naughty. He is making some changes in the names of naughty children. He can perform three type of queries:

1. 1 id pos c: 1 denotes that this is the first type of query. In this query he will change the character in $id^{th}$ in position $pos$ to c, i.e. $P_{id,pos} = c$
2. 2 id c: 2 denotes that this is second type of query. In this query he will append the character c at the end of $P_{id}$.
3. 3 id: 3 denotes that this is third type of query. In this query, he will have to find how many names of nice children have $P_{id}$ as substring.

Input format:
First line contains an integer, N, denoting the number of nice children. Next N lines contains the names of the N nice children. Next line contains an integer, M, denoting the number of naughty children. Next M lines contains the names of the M naughty children. Next line contains an integer, Q $(1 \le Q \le 2 * 10^5)$, denoting the number of queries. Next Q lines contains one of the three types of queries.

Sum of lengths of all the $S_i \le 2 * 10^5$. Sum of lengths of all the $P_i \le 2 * 10^5$.

All the indexing will be 1-based.

All $S_i$ and $P_i$ are not empty.

Output format:
For each third type query, print an integer, denoting the answer of the third query.

SAMPLE INPUT
3
aa
ab
aac
2
a
a
5
3 1
2 2 b
3 2
1 2 2 a
3 2
SAMPLE OUTPUT
3
1
2
Explanation
1. First a is substring of $aa$, $ab$, $aac$. So answer is 3.
2. Second a is now $ab$.
3. $ab$ is substring of $ab$. So answer is 1.
4. $ab$ is $aa$ now.
5. $aa$ is substring of $aa$, $aac$. So answer is 2.
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Christmas Circuits '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Graphs