Additional explanation of the solution, requested by ehsanoo. On the contrary to the tutorial, we will apply the queries online (however result itself will be calculated offline anyway; after you understand this part, you can revert the construction to obtain the solution described in the tutorial). We will keep our string in a compressed form of a DAG.

• The DAG on the left represents the string from the first sample test: 123123. Note that the root consists of 6 cells. Each represents a digit of 123123, however their values are not stored there. Each cell points to the leaf corresponding to its content. Note that cells corresponding to the same digit point to the same leaf.
• Now the first query comes: 2->00, so our string should become 10031003. What we do? We grab our leaf '2' and replace it with a new node (with 2 cells pointing to 0). Everything what was pointing to '2' now points to our new node (i.e. we replaced all occurrences of '2').
• Note that we create a new leaf '2' (marked as red). In general case the replacing string can contain the digit which is being replaced and we don't want the node to point to itself (i.e. we are not doing a recursive replacement).

To sum up: every node of the DAG represents some substring of the current string. At any point of processing the queries, we keep track of nodes which correspond to the single digits, so that we can replace them with a string from a query. For the replaced digit we create a new node and from now on, any new occurrences of this digit should point to this new node. At any point we can retrieve the current string by traversing the DAG. After processing all the queries we want to retrieve the result. To do that, we can dynamically calculate 2 values for each node:

• the number it represents mod (10⁹ + 7)
• mod (10⁹ + 7)

It is easy to see how to calculate them for the parent, if we already calculated them for the children.

Formal proof on how many weapon levels can be neglected.

Let us take k = 1 and denote the stopping time of obtaining a weapon of cost i as . Then

independent

We can bound from below the geometric distriubtion by uniform one, in a sense that

independent

where is exactly an event in which we eventually obtain a weapon of level x. Now let us present the probability space of Y₁, .., Y_x as Ω = [0, 1] × [0, 2] × .. × [0, x] which is a hypercuboid with volume x!, therefore probability measure P has density in lebesgue measure. It is easy to see that is contained in a hypercone of lebesgue volume . By taking into consideration the density g, we get an upper bound

Now back to the original task. Let us denote the total profit from selling the weapons as T ≤ n². We want the following expectation to be small:

For n = 10⁵ and ε = 10^- 9, using the formula above we can check that x = 900 is enough.