#P18817. [Croatian CPC2015] Piramida

[Croatian CPC2015] Piramida

[Croatian CPC2015] Piramida

题目描述

Mirko 和 Slavko 在沙漠中发现了一座金字塔。门上的控制台给出了六个整数 n,v,a,b,c,mn,v,a,b,c,m,用来生成一个具有 nn 行的三角形数表。第 ii 行有 ii 个数,第 jj 个数记为 p(i,j)p(i,j)。

数表按以下规则生成:

p(1,1)=v,p(1,1)=v, $$p(i,1)=\bigl(c\cdot p(i-1,1)\bigr)\bmod m\qquad(2\le i\le n),$$$$p(i,j)=\bigl(a\cdot p(i,j-1)+b\cdot p(i-1,j-1)\bigr)\bmod m \qquad(2\le i\le n,\ 2\le j\le i).$$

金字塔及子金字塔示意图

随后有 qq 次询问。每次询问给出 r,s,xr,s,x,表示顶端位于 (r,s)(r,s)、边长为 xx 的子金字塔。它包含第 r+tr+t 行中从第 ss 个到第 s+ts+t 个位置的数,其中 0≤t<x0\le t<x。

例如,图中红色边框表示 r=2,s=2,x=2r=2,s=2,x=2 的子金字塔。

对于每次询问,请输出对应子金字塔中所有数的最大值。

输入格式

第一行包含六个整数 n,v,a,b,c,mn,v,a,b,c,m,满足:

  • 1≤n≤40001\le n\le4000;
  • 1≤v,a,b,c≤1091\le v,a,b,c\le10^9;
  • 2≤m≤1092\le m\le10^9。

第二行包含一个整数 qq(1≤q≤5000001\le q\le500000)。

接下来 qq 行,每行包含三个整数 r,s,xr,s,x,满足 1≤r≤n1\le r\le n,1≤s≤r1\le s\le r,1≤x≤n−r+11\le x\le n-r+1。

输出格式

输出 qq 行,每行一个整数,依次表示对应询问的答案。

样例 1

输入

3 1 1 1 1 3
2
1 1 1
1 1 2

输出

1
2

样例 2

输入

5 3 1 1 1 5
4
1 1 1
3 3 2
1 1 4
2 1 1

输出

3
4
4
3

样例 3

输入

34 72 111 13 17 912131
5
17 17 9
17 9 10
11 10 8
13 9 1
3 3 30

输出

877499
896373
838846
429006
911914

样例说明

样例 2 生成的数表为:

3
3 1
3 1 2
3 1 2 4
3 1 2 4 3

第二次询问的子金字塔包含 p(3,3)=2p(3,3)=2、p(4,3)=2p(4,3)=2 和 p(4,4)=4p(4,4)=4,因此答案为 44。