Персистентний список
Задано 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.