Недалёкое Будущее. Ямочка работает на заводе по печатанию строк. Сейчас перед ней стоит задача напечатать строку S. Чтобы справиться с работой, Ямочка выбирает непустой префикс S длины l, после чего печатает его несколько раз подряд. Количество повторений и длину l она выбирает так, чтобы получившаяся строка равнялась исходной S. Чтобы напечатать префикс один раз, Ямочке требуется l² секунд.

Если Ямочка долго работает над одной и той же задачей, то начинает расслабляться и постепенно сбавлять темпы производства, что очень не нравится её начальнику Вадиму, который, в свою очередь, имеет набор из M строк t_i. Чтобы добиться максимальной продуктивности от своего работника, Вадим время от времени берёт строку t_kj из набора и выбирает индекс p_j, после чего заменяет подстроку S_pj S_pj+1 … S_pj+|tkj|−1 на t_kj. Например, если S = «aboba», t_kj = «pupa» и p_j = 2, то в результате S станет равна «apupa».

Ямочка ещё молодая, поэтому хочет работать как можно меньше. Помогите ей: для изначальной строки и после каждого изменения скажите минимальное время, необходимое для печати S.

В первой строке дано три целых числа N, M и Q — длина строки S, количество строк в наборе Вадима и количество изменений (1 ≤ N ≤ 2 · 10⁵, 0 ≤ M, Q ≤ 2 · 10⁵).

В следующей строке дана изначальная строка S из строчных английских букв.

В следующих M строках даны непустые строки t_i — набор Вадима (1 ≤ |t_i| ≤ 10⁶). Гарантируется, что суммарная длина строк из набора не превосходит 10⁶.

В следующих Q строках описаны изменения двумя целыми числами p_j и k_j — начало отрезка и номер строки из набора (1 ≤ p_j ≤ N − |t_kj| + 1, 1 ≤ k_j ≤ M).

В первой строке выведите минимальное необходимое время до всех изменений. В следующих Q строках выведите минимальное время после соответствующего изменения.

После первого изменения строка станет равна «abbe». После второго — «ebbe». После третьего — «eeee».