问题描述
有一条长度为$n$的链. 节点$i$和$i+1$之间有长度为$1$的边. 现在又新加了3条边, 每条边长度都是1. 给出$m$个询问, 每次询问两点之间的最短路.
输入描述
输入包含多组数据. 第一行有一个整数$T$, 表示测试数据的组数. 对于每组数据:
第一行包含2个整数$n$和$m$ $(1 \le n,m \le 10^5)$表示节点的数目和询问数目. 接下来一行包含$6$个有空格分开的整数$a_1, b_1, a_2, b_2, a_3, b_3$ $(1 \le a_1,a_2,a_3,b_1,b_2,b_3 \le n)$, 表示新加的三条边为$(a_1,b_1)$, $(a_2,b_2)$, $(a_3,b_3)$. 接下来$m$行, 每行包含两个整数$s_i$和$t_i$ $(1 \le s_i, t_i \le n)$, 表示一组询问.
所有数据中$m$的和不超过$10^6$.
输出描述
对于每组数据, 输出一个整数$S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$, 其中$z_i$表示第$i$组询问的答案.
输入样例
1
10 2
2 4 5 7 8 10
1 5
3 1
输出样例
7
