industriouslibrarian

Industrious Librarian

Garrytown University has an Imperial Library, and Xiaodou is the librarian maintaining the library's reading room.

Xiaodou's task is to keep the books arranged in an orderly manner, and so books in the wrong order make him bored. In particular, when a pair of books is out of order, that pair makes Xiaodou bored by the sum of pages of those two books.

There are n books in the room, and on each of the next m days, a pair of books will be taken out by a reader and placed back with swapped positions.

Xiaodou is required to sort all the books at least once over the next m days. As a result, he would like to know how much boredom he will face at the end of each of these days, assuming he has not sorted the books yet - so that he can pick the day where he faces the least boredom to sort them.

Input format

The first line of input consists of two integers, n and m.
n lines of input follow. The ith of these lines contains 2 integers ai and vi, denoting that the book currently in position i belongs in position ai, and has vi pages. It is guaranteed that no two books will belong in the same position.
m lines of input follow. The jth of these lines contains 2 integers xj and yj, denoting that on the jth day, the books in positions xj and yj switch places after a reader reads them.

Output format

Output m lines each containing a single integer, the ith of which shall be the boredom Xiaodou faces at the end of the ith day. As this number may be large, output its value modulo 109+7.

Limits

1ai,xj,yjn50000.
0vi105.
Subtask # Score Constraints
1 8 n,n2000
2 16 n,m5000
3 48 n,m40000
4 28 No additional constraints

Samples

Sample Input 1 Sample Output 1
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


Submitting to 'industriouslibrarian'


You're not logged in! Click here to login


Submitting to 'industriouslibrarian'


You're not logged in! Click here to login


Submitting .cpp to 'industriouslibrarian'


You're not logged in! Click here to login

Time Limit: 3.5 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: LOJ #2639

Subtask Score
1 8
2 16
3 48
4 28