题目描述

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。

他的任务是把书排成有序的，所以无序的书让他产生厌烦。

两本乱序的书会让小豆产生这两本书页数的和的厌烦度。

现在有 $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$ 后输出。

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\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$。