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.
The first line of input consists of two integers, \(n\) and \(m\).
\(n\) lines of input follow. The \(i^{th}\) of these lines contains 2 integers \(a_i\) and \(v_i\), denoting that the book currently in position \(i\) belongs in position \(a_i\), and has \(v_i\) pages. It is guaranteed that no two books will belong in the same position.
\(m\) lines of input follow. The \(j^{th}\) of these lines contains 2 integers \(x_j\) and \(y_j\), denoting that on the \(j^{th}\) day, the books in positions \(x_j\) and \(y_j\) switch places after a reader reads them.
Output \(m\) lines each containing a single integer, the \(i^{th}\) of which shall be the boredom Xiaodou faces at the end of the \(i^{th}\) day. As this number may be large, output its value modulo \(10^9 + 7\).
Subtask #  Score  Constraints 

1  8  \(n, n \leq 2000\) 
2  16  \(n, m \leq 5000\) 
3  48  \(n, m \leq 40000\) 
4  28  No additional constraints 
Sample Input 1  Sample Output 1 
5 5

42

Subtask  Score 

1  8 
2  16 
3  48 
4  28 