1448 - 树状数组

<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 省选 高级

Time Limit 4 seconds
Memory Limit 512 MB
Discuss Stats
上一题 下一题