Book

Xzz is a librarian in the reading room whose task is to keep the books in order and disordered books make him feel boring. Two books in wrong order bore him as many as the total pages of two books. Now there are n books that in wrong order. The boredom of Xzz:

In the next m days, the order of the books will be changed by readers. Because Xzz is asked to organize the books for at least one time in the next m days, he wants to know his boredom of each day if he doesn't organize the books. So he would organize books at that day.

First line of the input file contains an integer T(0 < T ≤ 10) that indicates how many cases of inputs are there.

The description of each case is given below:

First line of the input file contains two integers, n and m, indicating the number of books and number of days.

Then follow n lines and each line contains two numbers, ord(i) and vi, indicating that the ith book should be placed in the ai position, and it has vi pages.

Then follow m lines and each line contains two numbers, xj and yj, indicating that the book in position xj will be exchanged with the book in position yj on the jth day.

For all the data: 1 ≤ ord(i), xj, yj ≤ n ≤ 5×10^4 , m ≤ 5×10^4, vi ≤ 10^5

The description of output for each test case is given below:

There should be m lines in total. The i-th line of the output contains one number B, means the boredom B of Xzz if he did not organize books in the first i days.

The result is too big, print the result module 10^9 + 7.

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