1454 - 不勤劳的图书管理员

通过次数

0

提交次数

0

时间限制 : 5 秒
内存限制 : 256 MB

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

输入

第一行会有两个数,n,m分别表示有n本书,m 天 

接下来n行,每行两个数,ai和vi,分别表示第i本书本来应该放在ai的位置,这 本书有vi页,保证不会有放置同一个位置的书

 接下来m行,每行两个数,xj和yj,表示在第j天的第xj本书会和第yj本书会因 为读者阅读交换位置

输出

一共m行,每行一个数,第i行表示前i天不去整理,第i天小豆的厌烦度,因 为这个数可能很大,所以将结果模109 + 7后输出 

样例

输入

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

提示

数据范围 

对于20%的数据,1 ≤ ai , xj , yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 105

对于100%的数据,1 ≤ ai , xj , yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 105

来源

TJOI2017 NOIP TJOI2017day1 高级