题目描述

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员. 他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。 现在有$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$天的第$xj$本书会和第$y_j$本书会因为读者阅读交换位置

输出

一共$m$行，每行一个数，第$i$行表示前$i$天不去整理，第$i$天小豆的厌烦度，因为这个数可能很大，所以将结果模$10^9 + 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 ≤ a_i , x_j , y_j ≤ n ≤ 5000, m ≤ 5000, v_i ≤ 10^5 $ 对于$100%$的数据，$1 ≤ a_i , x_j , y_j ≤ n ≤ 50000, m ≤ 50000, v_i ≤ 10^5$