Persistent list
Given n lists, each containing a single element, you need to perform the following operations:
merge — Combine any two existing lists to create a new list that is the concatenation of the two.
head — Take an existing list L and create two new lists: one containing the first element of L, and the other containing all elements of L except the first.
tail — Take an existing list L and create two new lists: one containing all elements of L except the last, and the other containing the last element of L.
For each newly created list, output the sum of its elements modulo 10^9 + 7.
Input
The input begins with the number n (1 ≤ n ≤ 10^5), followed by n integers ranging from 1 to 10^9, which are the elements of the lists. The initial lists are numbered 1, 2, ..., n.
Next, the number m (1 ≤ m ≤ 10^5) is given, representing the number of operations. The operations are specified in the following format:
merge i j
head i
tail i
Here, i and j refer to the numbers of existing lists. If there are currently k lists, the new list is assigned the number k+1.
For the head and tail operations, the left part is generated first, followed by the right part (refer to the example). It is guaranteed that no empty lists will be created.
Output
For each new list, print the sum of its elements modulo 10^9 + 7.