The first thing to do is root the tree, for which we can arbitrarily choose node \(1\). Each journey can be done in two phases:
1. *Uplifting*: \(k_1\) steps in root's direction (\(k_1\) can be zero).
2. *Descent*: \(k_2\) steps in the opposite direction (\(k_2\) can be zero, \(k_1 + k_2 \le K_i\)).

Indeed, after we descend one step, there is no way to start moving up, because the previous edge will always be the edge we need to go upwards (and we can't traverse an edge twice).

Next, notice that adding new nodes don't make the problem significantly harder. We can preprocess all type-1 events and construct the full tree, then process events of both types in reverse order: it's easier to remove nodes rather than to add them. For a reverse type-1 event, we'll replace the node with a reference to its parent so that whenever we get to this node, we instantly return to its parent. For some removals, we must repeat until we reached a node that still exists in the tree. A disjoint set union (DSU) data structure can be used to perform these operations efficiently. For each node, we'll use DSU to find the bottommost ancestor that still exists in the tree.

Now, we'll need a way to perform phase 1 and phase 2 in time faster than \(\mathcal{O}(N + Q)\). For simplicity, we'll describe the solution for an indefinite \(K\). If the destination node is known, we can always backtrack a certain number of steps using binary lifting.

*Phase 1.* In this problem, we have an radix size of \(R = 26\), so we have only \(26 * 25 = 650\) unique pairs of letters. Let's call a pair of letters \((c_1, c_2)\) *active* if \(c_1\) precedes \(c_2\) in the given string \(S_i\). For each edge and pair of letters, we can precompute the ancestor node where the uplifting ends (due to this pair being active) using depth-first search in \(\mathcal{O}((N + Q) * R^2)\). If we start at some node \(v\) and we need to find the node where uplifting stops, we should do the following:

1. Start uplifting at node \(v\). Look through all the edges adjacent to \(v\) to make sure the first edge of the traversal will be the edge to its parent. If not, there is no uplifting for the current event.
2. Iterate over all active pairs and pick the bottommost precomputed node across all these pairs for the edge from node \(v\) to its parent. This node is the destination of uplifting.

The total complexity for phase 1 of a single journey is \(\mathcal{O}(R^2)\). We only iterate over at most \(R\) edges and over at most \(R * (R - 1) / 2\) pairs.

*Phase 2.* This phase is slightly more difficult because we have to pick the right edge by ourselves (where in phase 1, we always took the edge from a node to its parent). One possible strategy is to consider the edge that leads to the largest subtree. For each node and pair of letters, we can precompute the descendant node where the descent ends due to this pair being active. The way we use this data is very similar to phase 1:

1. Start the descent at node \(v\).
2. Iterate over all active pairs and pick the topmost precomputed node \(u\) across all these pairs for the vertex \(v\). It's possible that \(u = v\).
3. Look through all edges adjacent to \(u\) for the next step. If there is no such edge, node \(u\) is the destination of our descent. Otherwise, this edge leads to the node we assign to \(v\), and we return to step 2.

Each time we perform step 3, we reduce the maximum possible number of steps left by at least a half, so at most we will repeat it \(\mathcal{O}(\log(N + Q))\) times for each journey. Since each such step takes \(\mathcal{O}(R^2)\) time, the overall time complexity for phase 2 of a journey is \(\mathcal{O}(\log(N + Q) * R^2)\), and the overall time complexity is therefore \(\mathcal{O}(Q * \log(N + Q) * R^2)\).