Description

At Jialidun University, there is an Imperial Library. Xiao Dou is a librarian in the library’s reading room. His job is to keep the books in order, so disorder annoys him. A pair of books that are out of order causes an annoyance equal to the sum of their page counts. There are $n$ books currently in a jumbled order. During the next $m$ days, readers’ use will cause the books’ positions to change each day. Xiao Dou is required to tidy the books at least once during these $m$ days. He wants to know, if he does not tidy during the first $i$ days, what his annoyance will be on day $i$, so that he can choose the day with the minimum annoyance to tidy.

Input Format

The first line contains two integers $n,m$, denoting $n$ books and $m$ days. The next $n$ lines each contain two integers $a_i,v_i$, meaning that book $i$ should be placed at position $a_i$, and this book has $v_i$ pages. It is guaranteed that no two books have the same intended position. The next $m$ lines each contain two integers $x_j$ and $y_j$, meaning that on day $j$, book $x_j$ and book $y_j$ swap positions due to readers’ usage.

Output Format

Output $m$ lines. The $i$-th line is the annoyance on day $i$ if he does not tidy during the first $i$ days. Since this number can be large, output the result modulo $10^9 +7$.

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

42
0
18
28
48

Hint

Constraints

• For $20\%$ of the testdata, $1\le a_i,x_j,y_j\le n \le 5\times 10^3$, $1\le m\le 5\times 10^3$, $1\le v_i\le10^5$.
• For $100\%$ of the testdata, $1\le a_i,x_j,y_j\le n\le 5\times 10^4$, $1\le m\le 5\times 10^4$, $1\le v_i\le 10^5$.

Translated by ChatGPT 5