#9247. [DAY09]二维曼哈顿激发 暂未评定

时间限制:2000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

33DAI 拿到了一个 列的二维数组。第 行第 列的元素用 表示。

他需要进行 次激发操作。每次激发操作都会给你三个参数 ,表示需要把与 的曼哈顿距离不超过 的点都增加

简单来说,如果 满足 ,那么就把 位置上的数增加

请你看看最终矩阵会变成什么样。

矩阵太大了,你只需要输出 ,即所有位置的“数和他们坐标之和的平方”之和模 之后的结果。

输入格式

第一行三个数,

接下来 行,第 行为空格隔开的三个整数 ,表示一次操作。

输出格式

一个数,即题目要求的答案。

样例

样例输入 1

8 8 3
3 3 3
7 8 2
8 1 2

样例输出 1

6515

数据范围与提示

对于 的数据,

  • 子任务 1(30 分):
  • 子任务 2(30 分):
  • 子任务 3(40 分):没有特殊限制。