4889 - [Tjoi2017]不勤劳的图书管理员

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

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

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

现在有 n 本被打乱顺序的书，在接下来 m 天中每天都会因为读者的阅览导致书籍顺序改变位置。

因为小豆被要求在接下来的 m 天中至少要整理一次图书。

小豆想知道，如果他前 i 天不去整理，第 i 天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

第一行会有两个数，n,mn,mn,m 分别表示有 nnn 本书，mmm 天。

接下来 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 后输出。

• 对于 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。