Near Future. Yamochka works at a string printing factory. She is currently tasked with printing the string S. To complete the job, Yamochka chooses a non-empty prefix of S of length l, after which she prints it several times in a row. She selects the number of repetitions and the length l such that the resulting string equals the original S. To print the prefix once, Yamochka requires l² seconds.

If Yamochka works on the same task for too long, she starts to relax and gradually slows down her production, which displeases her boss Vadim, who has a set of M strings t_i. To achieve maximum productivity from his worker, Vadim occasionally takes a string t_kj from the set and selects an index p_j, after which he replaces the substring S_pj S_pj+1 … S_pj+|tkj|−1 with t_kj. For example, if S = “aboba”, t_kj = “pupa” and p_j = 2, then as a result, S will become “apupa”.

Yamochka is still young, so she wants to work as little as possible. Help her: for the initial string and after each modification, tell her the minimum time required to print S.

The first line contains three integers N, M and Q — the length of the string S, the number of strings in Vadim’s set, and the number of modifications (1 ≤ N ≤ 2 · 10⁵, 0 ≤ M, Q ≤ 2 · 10⁵).

The next line contains the initial string S consisting of lowercase English letters.

The following M lines contain non-empty strings t_i — Vadim’s set (1 ≤ |t_i| ≤ 10⁶). It is guaranteed that the total length of the strings in the set does not exceed 10⁶.

The next Q lines describe the modifications with two integers p_j and k_j — the start of the segment and the index of the string from the set (1 ≤ p_j ≤ N − |t_kj| + 1, 1 ≤ k_j ≤ M).

In the first line, output the minimum required time before any modifications. In the following Q lines, output the minimum time after each corresponding modification.

After the first modification, the string will become “abbe”. After the second — “ebbe”. After the third — “eeee”.