How about we characterize a casualty substance: a casualty has a name (not really extraordinary) that comprises just of lowercase Latin letters and an integer doubt esteem. Toward the beginning of the program the client enters a rundown of n casualty names into an information base, every
Correct answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science.
How about we characterize a casualty substance: a casualty has a name (not really extraordinary) that comprises just of lowercase Latin letters and an integer doubt esteem.
Toward the beginning of the
Then, at that point, the client makes questions of two sorts:
1 I x — set the doubt worth of the I-th casualty to x;
2 q — given a string q observe the most extreme doubt worth of a casualty whose name is a coterminous substring of q.
Just to remind you, this program doesn't eliminate individuals, it just assists with looking for the names to record in a genuine scratch pad. Consequently, the rundown of the casualties in the data set doesn't change all through the questions.
What are you sitting tight for? Compose that program now!
Input
The main line contains two integers n and m (1≤n,m≤3⋅105) — the number of casualties and the number of inquiries, individually.
Every one of the following n lines contains a solitary string si — the name of the I-th casualty. Each name comprises just of lowercase Latin letters.
Every one of the following m lines contains a question of one of two kinds:
1 I x (1≤i≤n, 0≤x≤109) — change the doubt worth of the I-th casualty to x;
2 q — given a string q comprising just of lowercase Latin letters observe the greatest doubt worth of a casualty whose name is a touching substring of q.
There is no less than one inquiry of the subsequent sort. The complete length of the strings si doesn't surpass 3⋅105. The complete length of the strings q doesn't surpass 3⋅105.
Output
For each inquiry of the subsequent sort print an integer esteem. In case there is no casualty name that is an adjacent substring of q, then, at that point, print −1. In any case, print the greatest doubt worth of a casualty whose name is a touching substring of q.
Step by step
Solved in 4 steps with 1 images
