题目背景

深空观测站正在校准一块巨大的能量阵列。阵列中每个位置的能量值并不是逐格存储的，而是由一条长度为 $n$ 的基础序列共同决定。为了寻找最强的局部能量区域，工程师需要在整个阵列中选出一个非空正方形区域，使其中所有数值之和尽可能大。

由于阵列规模可达 $10^5\times 10^5$，显然无法把它完整构造出来。你需要利用阵列的特殊结构完成计算。

题目描述

给定一个 $n\times n$ 的矩阵 $A$。矩阵由一个长度为 $n$ 的整数序列 $B$ 构造，满足

$$A_{i,j}=B_i+B_j,$$

其中下标均从 $0$ 开始。

一个大小为 $m\times m$ 的正方形子矩阵，是由连续的 $m$ 行和连续的 $m$ 列组成的区域，其中 $1\le m\le n$。正方形子矩阵不能为空。

请你求出矩阵 $A$ 的所有非空正方形子矩阵中，元素总和的最大值。

序列 $B$ 通过下面三个步骤得到。

第一步：生成初始序列

输入给出整数 $n$、随机种子 $s$、模数 $q$ 和偏移量 $o$。按照下面的伪代码生成 $B$：

for i = 0..n-1:
    B[i] = (s div 2^20) modulo q + o

    s0 = (s * 621) modulo 2^51
    s1 = (s * 825) modulo 2^51
    s2 = (s * 494) modulo 2^51
    s3 = (s *  23) modulo 2^51

    s = s3
    s = (s * 2^10 + s2) modulo 2^51
    s = (s * 2^10 + s1) modulo 2^51
    s = (s * 2^10 + s0 + 11) modulo 2^51

其中：

• div 表示整数除法，例如 $49\mathbin{\mathrm{div}}10=4$；
• modulo 表示取模；
• $s_0,s_1,s_2,s_3$ 是临时变量；
• 上述所有运算均可使用有符号 $64$ 位整数安全完成。

生成出的每个 $B_i$ 都位于 $[o,o+q-1]$ 内。

第二步：修改序列

输入给出 $k$ 次修改。第 $i$ 次修改把

$$B_{x_i}$$

直接改为 $y_i$。所有位置下标均从 $0$ 开始。

第三步：构造矩阵

对于所有 $0\le i,j<n$，定义

$$A_{i,j}=B_i+B_j.$$

你不需要、也不应该显式构造整个矩阵 $A$。

输入格式

第一行包含四个整数

n s q o

第二行包含一个整数 $k$，表示修改次数。

接下来 $k$ 行，每行包含两个整数

x_i y_i

表示令 $B_{x_i}=y_i$。

输出格式

输出一个整数，表示所有非空正方形子矩阵的最大元素和。

数据范围

对于所有测试数据：

• $1\le n\le 10^5$；
• $0\le s\le 2^{51}-1$；
• $1\le q\le 10^8+1$；
• $-10^8\le o\le 10^8-q+1$；
• $0\le k\le 500$；
• $0\le x_1<x_2<\cdots<x_k<n$；
• $-10^8\le y_i\le 10^8$。

答案保证可以使用有符号 $64$ 位整数表示。

样例 1

输入

6 10000000014 20 -12
1
1 3

输出

28

说明

生成并修改后的序列为

$$B=\{4,3,-9,-7,5,2\}.$$

对应矩阵为

 8   7  -5  -3   9   6
 7   6  -6  -4   8   5
-5  -6 -18 -16  -4  -7
-3  -4 -16 -14  -2  -5
 9   8  -4  -2  10   7
 6   5  -7  -5   7   4

右上角的 $2\times 2$ 子矩阵元素和为

$$9+6+8+5=28,$$

且不存在元素和更大的正方形子矩阵。

样例 2

输入

7 10000000029 20 -12
0

输出

12

样例 3

输入

10 42 40 -5
0

输出

2660