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 \(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 format

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\).

Limits

\(1 \leq a_i, x_j, y_j \leq n \leq 50000\).
\(0 \leq v_i \leq 10^5\).

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

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