异或炸弹（hard）
题号：NC273583
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

此题为D题的hard版本，与D题仅有m的取值范围不同
给定一个的矩阵，初始全是 ，

现在文文手上有  个炸弹,

对于每一个炸弹，都有自己的 爆炸中心 和 爆炸半径 .

当矩阵内某个位置与爆炸中心的 曼哈顿距离 小于等于  时，该位置就会收到爆炸的影响， 爆炸的影响就是给这个位置上的数异或 .

文文给你这  个炸弹的爆炸位置和爆炸半径，你需要回答文文这个矩阵中  的个数

如果不明白 异或操作 和 曼哈顿距离，请看最后的提示

输入描述:

第一行给定两个正整数 , 分别表示矩阵大小和炸弹数量 
接下来行，每行个正整数其中第  行的前2个正整数  表示第  个炸弹的爆炸中心最后一个正整数  表示第  个炸弹的爆炸半径
1 ⩽ x_i, y_i ⩽ n
0 ⩽ r_i ⩽ 6000

输出描述:

输出被轰炸后的矩阵中  的个数
示例1

输入

复制 
5 1
3 3 1

输出

复制 
5

说明

案例解释
0 0 0 0 0
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
共有5个1 

备注:

关于异或的运算
0 ^ 1 = 1
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0

关于曼哈顿距离的运算如果两个点的坐标分别是 那么两个点的曼哈顿距离.