Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Besides numbers Alice also likes to play with cubes of letters.
She has infinite supply of the cubes with every lowercase Latin letter written on it. So she often builds the towers from her cubes.
Specifically, there are N initially empty towers of cubes. Step-by-step, Alice picks a cube and puts it to the top of some of the towers.
Sometimes she becomes curious about how many towers contain some of her M favorite words (not necessarily real English words).
Alice considers that a tower contains a word in case this word can be read on some consecutive "subtower" of this tower in up-down direction. For example, if Alice puts cubes with letters a, b, c, d (in this order) to the top of the tower, then the tower contains words cba or dc and doesn't contain words abcd, e.
But now the towers has grown very large, so Alice asks you to help her. There will be three types of queries given to you:
- 0 X C: put the cube with letter C to the top of the Xth tower.
- 1 L R P: find the number of towers in the range [L, R] which contain the Pth favorite word.
- 2 L R P: find the number of ways to pick a tower in the range [L; R] and then to read an occurrence of the Pth favorite word at this tower. Two ways are considered different, if the tower or if the topmost cube position of the occurrence are different.
Please help Alice.
The first line of the input contains three space-separated integers N, M and Q denoting the number of towers, the number of Alice's favorite words and the number of queries respectively.
Each of the following M lines contains a lowercase Latin letters string wi, denoting the ith favorite word of Alice.
Each of the following Q lines contains a query in one of the formats described above.
For each query of the type 1 or 2, output the answer on the separate line.
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 2 × 105
- 1 ≤ X ≤ N
- 1 ≤ L ≤ R ≤ N
- 1 ≤ P ≤ M ≤ 65536
- 1 ≤ sum of |wi| ≤ 65536
- All wi's are different.
- C is a lowercase Latin letter
- wi contains only lowercase Latin letters
- There will be no more than 65536 queries of the type 0.
Input: 3 2 10 a ab 0 1 a 1 1 2 1 0 2 a 1 1 2 1 1 1 2 2 0 1 a 2 1 3 1 0 1 b 1 1 2 2 2 2 3 1 Output: 1 2 0 3 0 1
- In the second query the only tower containing the word a is the tower 1
- In the fourth query the towers containing the word a are towers 1 and 2
- In the fifth query there is no even a single tower containing the word ab
- In the seventh query there are two ways to read the word a at the tower 1 (starting at the topmost or at the bottommost cube), one way to read the word a at the tower 2 (since this tower consists only of one cube with letter a) and zero ways to read the word a at the tower 3 (since it's empty)
- In the ninth query there is no way to read the word ab from any tower. Please pay attention that if we try to read a two-letter word from the top of the first tower, we will get ba and not ab
- In the tenth query the only tower containing the word a is the tower 2, and since it consists only of one cube with letter a, there is surely only one way to read this word
|Tags||medium-hard, range-tree, snckel16, xcwgf666|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions