Good Expressions

Петя и хорошие выражения.
Петя очень любит изучать сложные разделы математики. Недавно он сформулировал новый термин - "хорошее выражение". "Хорошим выражением" для Пети является всякое выражение вида a[1]^b[1] * a[2]^b[2] * ... * a[n]^b[n]) (a[i] обозначает не число, а номер элемента, т.е. i-ый член равен j-му, если a[i] = a[j]. Если a[i] != a[j], считайте i-ый и j-ый член взаимно простыми). Петя решил, что изучение "хороших выражений" поможет ему совершить прорыв в математике и начал работать над ними. Пока что он определил для "хороших выражений" одну операцию: UP(l, r, k), которая возводит все члены выражения с a[l] по a[r] включительно в степень k.
Сейчас Петя работает над одним из таких выражений. Поскольку Петя не очень аккуратен в своей работе, выражение у него записано как попало, и некоторые члены могут встречаться несколько раз. Пете интересно узнать:
- сколько различных (в математическом смысле) выражений можно получить, применяя операцию UP с известным параметром k ко всем возможным последовательным подвыражениям
- также для любого "хорошего выражения" Петя определяет параметр "хорошести" - это сумма всех b[i] в выражении. Найдите сумму параметров "хорошести" по всем различным (в математическом смысле) подвыражениям из прошлой подзадачи
- (*) Петя решил, что операция UP в текущем виде не очень широко применима и определил операцию ASC(k), которая позволяет возводить в степень k любое (не обязательно последовательное) подвыражение. Решите пункты 1, 2, где операция UP заменена на ASC
Входные данные:
n, k - длина исходного "хорошего выражения"
В следующих n строках задаются a[i] (1 <= a[i] <= n), b[i].
Найдите самое эффективное решение.