#923. [Lydsy1708月赛]小Q的方格纸

[Lydsy1708月赛]小Q的方格纸

Description

方格纸与草稿纸一样,都是算法竞赛中不可或缺的重要工具。身经百战的小Q自然也会随身带着方格纸。小Q的方格

纸有n行m列,一共n*m个方格,从上到下依次标记为第1,2,...,n行,从左到右依次标记为第1,2,...,m列,方便起

见,小Q称第i行第j列的方格为(i,j)。小Q在方格纸中填满了数字,每个格子中都恰好有一个整数a_{i,j}。小Q不

喜欢手算,因此每当他不想计算时,他就会让你帮忙计算。小Q一共会给出q个询问,每次给定一个方格(x,y)和一

个整数k(1<=k<=min(x,y)),你需要回答由(x,y),(x-k+1,y),(x,y-k+1)三个格子构成的三角形边上以及内部的所有

格子的a的和。

Format

Input

第一行包含6个正整数n,m,q,A,B,C(1<=n,m<=3000,1<=q<=3000000,1<=A,B,C<=1000000)

其中n,m表示方格纸的尺寸,q表示询问个数。

为了防止输入数据过大,a和询问将由以下代码生成:

unsigned int A,B,C;

inline unsigned int rng61(){

A ^= A << 16;

A ^= A >> 5;

A ^= A << 1;

unsigned int t = A;

A = B;

B = C;

C ^= t ^ A;

return C;

}

int main(){

scanf("%d%d%d%u%u%u", &n, &m, &q, &A, &B, &C);

for(i = 1; i <= n; i++)

    for(j = 1; j <= m; j++)

        a[i][j] = rng61();

for(i = 1; i <= q; i++){

    x = rng61() % n + 1;

    y = rng61() % m + 1;

    k = rng61() % min(x, y) + 1;

}

}

Output

为了防止输出数据过大,设f_i表示第i个询问的答案,则你需要输出一行一个整数,即:

(sum_{i=1}^q 233^{q-i}*f_i) mod 2^{32}

Samples

3 4 5 2 3 7
3350931807