Персистентный список
Заданы n списков, каждый из которых состоит из одного элемента. Необходимо научиться совершать следующие операции:
merge — взять два каких-то уже существующих списка и породить новый, равный их конкатенации.
head — взять какой-то уже существующий список L и породить два новых, в одном первый элемент L, во втором весь L кроме первого элемента.
tail — взять какой-то уже существующий список L и породить два новых, в одном весь L кроме последнего элемента, во втором последний элемент L.
Для свежесозданных списков нужно говорить сумму элементов в них по модулю 10^9 + 7.
Входные данные
Число n (1 ≤ n ≤ 10^5). Далее n целых чисел от 1 до 10^9 - элементы списков. Исходные списки имеют номера 1, 2, ..., n.
Затем число m (1 ≤ m ≤ 10^5) - количество операций. Далее даны операции в следующем формате:
merge i j
head i
tail i
где i и j - номера уже существующих списков. Если в текущий момент имеется k списков, новый список получает номер k+1.
Для операций head и tail считается, что сперва порождается левая часть, затем правая (см. пример). Также Вам гарантируется, что никогда не будут порождаться пустые списки.
Выходные данные
Для каждого нового списка нужно вывести сумму элементов по модулю 10^9 + 7.