[Ynoi2014] 等这场战争结束之后

输入输出样例

输入样例 #1

6 10
816801151 223885531 110182151 94271893 319888699 106363731
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

输出样例 #1

94271893
223885531

说明

Idea：nzhtl1477， Solution：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time ，$O(n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) , zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ) Code：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time ，$O( n\log n )$ Space )，zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ) Data：nzhtl1477( partially uploaded ) 对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$0\leq a_i\leq 10^9$。