Пусть \(\text{LCP}(s, t)\) будет длиной наидлиннейшего общего префикса строк \(s\) и \(t\). Также назовем \(s[x \dots y]\) подстрокой \(s\) с позиции \(x\) до позиции \(y\) (включительно). Например, если \(s = \) «abcde», то \(s[1 \dots 3] =\) «abc», \(s[2 \dots 5] =\) «bcde».
Задана строка \(s\) длины \(n\), а также \(q\) запросов. Каждый запрос — это пара множеств целых чисел \(a_1, a_2, \dots, a_k\) и \(b_1, b_2, \dots, b_l\). Посчитайте \(\sum\limits_{i = 1}^{i = k} \sum\limits_{j = 1}^{j = l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])}\) для каждого запроса.
Выходные данные
Выведите \(q\) целых чисел — ответы на запросы в том же порядке, в каком запросы подавались во входных данных.
Примечание
Рассмотрим запросы:
- В первом запросе участвуют \(s[1 \dots 7] = \text{abacaba}\) и \(s[2 \dots 7] = \text{bacaba}\). Ответ равен \(\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{bacaba}) + \text{LCP}(\text{bacaba}, \text{abacaba}) + \text{LCP}(\text{bacaba}, \text{bacaba}) = 7 + 0 + 0 + 6 = 13\).
- Во втором запросе участвуют \(s[1 \dots 7] = \text{abacaba}\), \(s[2 \dots 7] = \text{bacaba}\), \(s[3 \dots 7] = \text{acaba}\) и \(s[7 \dots 7] = \text{a}\). Ответ равен \(\text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2\).
- В третьем запросе \(s[1 \dots 7] = \text{abacaba}\) сравнивается со всеми суффиксами. Ответ состоит из следующих ненулевых значений: \(\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{acaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{abacaba}, \text{a}) = 7 + 1 + 3 + 1 = 12\).
- В четвертом запросе участвуют \(s[1 \dots 7] = \text{abacaba}\) и \(s[5 \dots 7] = \text{aba}\). Ответ равен \(\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{aba}, \text{abacaba}) + \text{LCP}(\text{aba}, \text{aba}) = 7 + 3 + 3 + 3 = 16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 4
abacaba
2 2
1 2
1 2
3 1
1 2 3
7
1 7
1
1 2 3 4 5 6 7
2 2
1 5
1 5
|
13
2
12
16
|