[TJOI2017] 不勤劳的图书管理员

题目描述

加里敦大学有个帝国图书馆,小豆是图书馆阅览室的一个书籍管理员。 他的任务是把书排成有序的,所以无序的书让他产生厌烦。 两本乱序的书会让小豆产生这两本书页数的和的厌烦度。 现在有 $n$ 本被打乱顺序的书,在接下来 $m$ 天中每天都会因为读者的阅览导致书籍顺序改变位置。 因为小豆被要求在接下来的 $m$ 天中至少要整理一次图书。 小豆想知道,如果他前 $i$ 天不去整理,第 $i$ 天他的厌烦度是多少,这样他好选择厌烦度最小的那天去整理。

输入输出格式

输入格式


第一行会有两个数,$n,m$ 分别表示有 $n$ 本书,$m$ 天。 接下来 $n$ 行,每行两个数,$a_i,v_i$,分别表示第 $i$ 本书本来应该放在 $a_i$ 的位置,这本书有 $v_i$ 页,保证不会有放置同一个位置的书。 接下来 $m$ 行,每行两个数,$x_j$ 和 $y_j$,表示在第 $j$ 天的第 $x_j$ 本书会和第 $y_j$ 本书会因为读者阅读交换位置。

输出格式


一共 $m$ 行,每行一个数,第 $i$ 行表示前 $i$ 天不去整理,第 $i$ 天小豆的厌烦度,因为这个数可能很大,所以将结果模 $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

输出样例 #1

42
0
18
28
48

说明

#### 数据规模与约定 - 对于 $20\%$ 的数据,$1\le a_i,x_j,y_j\le n \le 5\times 10^3$,$1\le m\le 5\times 10^3$, $1\le v_i\le10^5$。 - 对于 $100\%$ 的数据,$1\le a_i,x_j,y_j\le n\le 5\times 10^4$,$1\le m\le 5\times 10^4$,$1\le v_i\le 10^5$。