样例输入1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

样例输出1

9
8
8
16
16

后两个样例见 此贴。