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 books in the room, and on each of the next 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 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, and .
lines of input follow. The of these lines contains 2 integers and , denoting that the book currently in position belongs in position , and has pages. It is guaranteed that no two books will belong in the same position.
lines of input follow. The of these lines contains 2 integers and , denoting that on the day, the books in positions and switch places after a reader reads them.
Output format
Output lines each containing a single integer, the of which shall be the boredom Xiaodou faces at the end of the day. As this number may be large, output its value modulo .
Limits
.
.
Subtask #
|
Score
|
Constraints
|
1 |
8 |
|
2 |
16 |
|
3 |
48 |
|
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
|