1448 - 树状数组

通过次数

0

提交次数

0

Time Limit : 4 秒
Memory Limit : 512 MB

<img src="http://tk.hustoj.com:80/upload/image/20180219/20180219191007_84289.jpg" alt="" /> 

Input

Output

Examples

Input

5 5
1 3 3
2 3 5
2 4 5
1 1 3
2 2 5

Output

1
0
665496236

Source

ZJOI2017 NOIP 省选 高级