Perhaps Strings Are Inevitable

As we can not update all the strings that have prefix $P$for each update query, we can hold the update for the time when it is required. That requires lazy propagation on trie. The idea is to save the information of the trie node which holds the last character of the given prefix to the node which holds the updated last character. whenever you visit a node of a trie, you just propagate lazily.

Time complexity: O(sum of characters * 26)