logo AlgoBeat OnlineJudge
登录 注册

#102877. [BZOJ 2877] [Noi2012]魔幻棋盘

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

题目描述

有一张 的网格,初始位置 上的值是给定的 ,网格上有一个位于 的基础点。

需要你维护这个网格,支持 次如下操作之一:

  • 0 x1 y1 x2 y2,询问以 为基础,向上扩展 行,向下扩展 行,向左扩展 ​ 列,向右扩展 列得到的矩阵里所有数字的最大公约数;
  • 1 x1 y1 x2 y2 c,对以 ​​ 为左上角, 为右下角的矩阵中的每个位置都加上 ​​。

输入格式

第一行两个正整数 表示网格大小。

第二行两个正整数 ​ 表示基础点的坐标。

第三行一个整数 表示操作次数。

接下来一个 列的矩阵表示初始每个位置上的值。

接下来 行,每行一个操作,操作格式见题目描述。

输出格式

对于每次询问操作,输出一行一个整数表示答案。

样例

样例输入 #1

2 2
1 1
4
6 12
18 24
0 0 0 1 0
1 1 1 1 2 6
1 2 1 2 2 6
0 0 0 1 1

样例输出 #1

6
6

数据范围与提示

对于 的数据,

对于另外 的数据,

对于剩余 的数据,

对于 ​​​ 的数据,​​ 始终是不超过 ​​ 的正整数,且在每种数据中均有一半的数据满足所有 修改 都有