Given 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 and create two new lists: one containing the first element of , and the other containing all elements of except the first.
tail — Take an existing list and create two new lists: one containing all elements of except the last, and the other containing the last element of .
For each newly created list, output the sum of its elements modulo 10^9 + 7.
The input begins with the number (1 \leq n \leq 10^5), followed by integers ranging from to 10^9, which are the elements of the lists. The initial lists are numbered 1, 2, \dots, n.
Next, the number (1 \leq m \leq 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, and refer to the numbers of existing lists. If there are currently 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.
For each new list, print the sum of its elements modulo 10^9 + 7.
Example 1