Persistent list#2957

Persistent list

2 seconds
256 megabytes
Medium

Given lists, each containing a single element, you need to perform the following operations:

For each newly created list, output the sum of its elements modulo 10^9 + 7.

Input

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.

Output

For each new list, print the sum of its elements modulo 10^9 + 7.

Examples

Example 1

Loading
Loading