题号：NC20596
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。现在有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天小豆的厌烦度，因为这个数可能很大，所以将结果模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
备注:
对于20%的数据，1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5
对于100%的数据，1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5