Xiao Dou is a librarian at the Imperial Library of Jialin University. His job is to keep the books in order, as an unordered collection of books makes him annoyed. Two out-of-order books will cause Xiao Dou a level of annoyance equal to the sum of their page counts. There are currently $n$ books in a jumbled order. Over the next $m$ days, the books will change positions every day because readers move them. Since Xiao Dou is required to tidy up the books at least once every $m$ days, he wants to know his total annoyance level before tidying up on each day $i$, so that he can choose the day with the minimum annoyance to tidy them up.

Input

The first line contains two integers $n$ and $m$, representing the number of books and the number of days, respectively.

The next $n$ lines each contain two integers $a_i$ and $v_i$, representing that the $i$-th book should originally be at position $a_i$, and this book has $v_i$ pages. It is guaranteed that no two books are at the same position.

The next $m$ lines each contain two integers $x_j$ and $y_j$, representing that on the $j$-th day, the books at position $x_j$ and position $y_j$ are swapped by readers.

Output

There are $m$ lines, each containing one integer. The $i$-th line represents Xiao Dou's annoyance level before tidying up on day $i$. Since this number can be very large, output the result modulo $10^9 + 7$.

Constraints

For 20% of the data: $1 \le a_i, x_j, y_j \le n \le 5000$, $m \le 5000$, $v_i \le 10^5$.

For 100% of the data: $1 \le a_i, x_j, y_j \le n \le 50000$, $m \le 50000$, $v_i \le 10^5$.

Examples

Input 1

5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3

Output 1

42
0
18
28
48