Pyramid

Time limit4sMemory limit512 MB

Summary

Build an n-row triangular pyramid from a linear recurrence, then answer queries for the maximum value inside a downward triangular sub-pyramid.

Level: Medium7 of 10
Topics: Dynamic programming, Array, Implementation
Solved: No attempts yet

Problem

Mirko and Slavko were walking through the desert when they came across a pyramid. A small console on its door shows a riddle made of six integers $n$ , $v$ , $a$ , $b$ , $c$ , $m$ . The door opens only after they build the pyramid those numbers describe and type it into the console.

The pyramid has $n$ rows. Row $i$ holds $i$ numbers $p(i,1)$ , $p(i,2)$ , $\dots$ , $p(i,i)$ , and every value follows these rules.

$p(1,1) = v$ . No modulo is applied here, so $p(1,1)$ stays equal to $v$ even when $v \ge m$ .
$p(i,1) = (c \times p(i-1,1)) \bmod m$ for $2 \le i \le n$
$p(i,j) = (a \times p(i,j-1) + b \times p(i-1,j-1)) \bmod m$ for $2 \le i \le n$ and $2 \le j \le i$

Once the door opens, the console asks $q$ questions. Each question consists of three integers $r$ , $s$ , $x$ and names the sub-pyramid whose top is $p(r,s)$ and whose side has length $x$ . That sub-pyramid holds every cell $p(i,j)$ with $r \le i \le r+x-1$ and $s \le j \le s+(i-r)$ . For example, the sub-pyramid given by $r=2$ , $s=2$ , $x=2$ consists of the three cells $p(2,2)$ , $p(3,2)$ , $p(3,3)$ , drawn in red in the picture. Answer each question with the largest number the sub-pyramid holds.

Input

The first line contains six integers $n$ , $v$ , $a$ , $b$ , $c$ , $m$ separated by spaces ( $1 \le n \le 4000$ , $1 \le v \le 10^9$ , $1 \le a \le 10^9$ , $1 \le b \le 10^9$ , $1 \le c \le 10^9$ , $2 \le m \le 10^9$ ).

The second line contains the number of questions $q$ ( $1 \le q \le 5 \times 10^5$ ).

Each of the next $q$ lines contains three integers $r$ , $s$ , $x$ ( $1 \le r \le n$ , $1 \le s \le r$ , $1 \le x \le n-r+1$ ).

Output

Print $q$ lines. Line $k$ contains the largest number inside the sub-pyramid named by the $k$ -th question.

Examples8

Example 1
Input
```
3 1 1 1 1 3
2
1 1 1
1 1 2
```
Expected output
```
1
2
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output

Example 4
Input
```
1 1 1 1 1 2
1
1 1 1
```
Expected output
```
1
```

Example 5

Input

2 1000000000 1 1 1 2
3
1 1 1
1 1 2
2 1 1

Expected output

1000000000
1000000000
0

Example 6

Input

12 7 999999999 1000000000 3 2
120
1 1 1
1 1 4
1 1 7
1 1 10
2 1 3
2 1 6
2 1 9
2 2 2
2 2 5
2 2 8
2 2 11
3 1 2
3 1 5
3 1 8
3 2 1
3 2 4
3 2 7
3 2 10
3 3 3
3 3 6
3 3 9
4 1 1
4 1 4
4 1 7
4 2 3
4 2 6
4 2 9
4 3 2
4 3 5
4 3 8
4 4 1
4 4 4
4 4 7
5 1 3
5 1 6
5 2 2
5 2 5
5 2 8
5 3 1
5 3 4
5 3 7
5 4 3
5 4 6
5 5 2
5 5 5
5 5 8
6 1 2
6 1 5
6 2 1
6 2 4
6 2 7
6 3 3
6 3 6
6 4 2
6 4 5
6 5 1
6 5 4
6 5 7
6 6 3
6 6 6
7 1 1
7 1 4
7 2 3
7 2 6
7 3 2
7 3 5
7 4 1
7 4 4
7 5 3
7 5 6
7 6 2
7 6 5
7 7 1
7 7 4
8 1 3
8 2 2
8 2 5
8 3 1
8 3 4
8 4 3
8 5 2
8 5 5
8 6 1
8 6 4
8 7 3
8 8 2
8 8 5
9 1 2
9 2 1
9 2 4
9 3 3
9 4 2
9 5 1
9 5 4
9 6 3
9 7 2
9 8 1
9 8 4
9 9 3
10 1 1
10 2 3
10 3 2
10 4 1
10 5 3
10 6 2
10 7 1
10 8 3
10 9 2
10 10 1
11 2 2
11 3 1
11 5 2
11 6 1
11 8 2
11 9 1
11 11 2
12 2 1
12 5 1
12 8 1
12 11 1

Expected output

Example 7

Input

40 1000000000 1000000000 999999999 999999937 1000000000
247
1 1 1
1 1 6
1 1 11
1 1 16
1 1 21
1 1 26
1 1 31
1 1 36
4 1 1
4 1 6
4 1 11
4 1 16
4 1 21
4 1 26
4 1 31
4 1 36
7 1 1
7 1 6
7 1 11
7 1 16
7 1 21
7 1 26
7 1 31
7 5 1
7 5 6
7 5 11
7 5 16
7 5 21
7 5 26
7 5 31
10 1 1
10 1 6
10 1 11
10 1 16
10 1 21
10 1 26
10 1 31
10 5 1
10 5 6
10 5 11
10 5 16
10 5 21
10 5 26
10 5 31
10 9 1
10 9 6
10 9 11
10 9 16
10 9 21
10 9 26
10 9 31
13 1 1
13 1 6
13 1 11
13 1 16
13 1 21
13 1 26
13 5 1
13 5 6
13 5 11
13 5 16
13 5 21
13 5 26
13 9 1
13 9 6
13 9 11
13 9 16
13 9 21
13 9 26
13 13 1
13 13 6
13 13 11
13 13 16
13 13 21
13 13 26
16 1 1
16 1 6
16 1 11
16 1 16
16 1 21
16 5 1
16 5 6
16 5 11
16 5 16
16 5 21
16 9 1
16 9 6
16 9 11
16 9 16
16 9 21
16 13 1
16 13 6
16 13 11
16 13 16
16 13 21
19 1 1
19 1 6
19 1 11
19 1 16
19 1 21
19 5 1
19 5 6
19 5 11
19 5 16
19 5 21
19 9 1
19 9 6
19 9 11
19 9 16
19 9 21
19 13 1
19 13 6
19 13 11
19 13 16
19 13 21
19 17 1
19 17 6
19 17 11
19 17 16
19 17 21
22 1 1
22 1 6
22 1 11
22 1 16
22 5 1
22 5 6
22 5 11
22 5 16
22 9 1
22 9 6
22 9 11
22 9 16
22 13 1
22 13 6
22 13 11
22 13 16
22 17 1
22 17 6
22 17 11
22 17 16
22 21 1
22 21 6
22 21 11
22 21 16
25 1 1
25 1 6
25 1 11
25 1 16
25 5 1
25 5 6
25 5 11
25 5 16
25 9 1
25 9 6
25 9 11
25 9 16
25 13 1
25 13 6
25 13 11
25 13 16
25 17 1
25 17 6
25 17 11
25 17 16
25 21 1
25 21 6
25 21 11
25 21 16
25 25 1
25 25 6
25 25 11
25 25 16
28 1 1
28 1 6
28 1 11
28 5 1
28 5 6
28 5 11
28 9 1
28 9 6
28 9 11
28 13 1
28 13 6
28 13 11
28 17 1
28 17 6
28 17 11
28 21 1
28 21 6
28 21 11
28 25 1
28 25 6
28 25 11
31 1 1
31 1 6
31 5 1
31 5 6
31 9 1
31 9 6
31 13 1
31 13 6
31 17 1
31 17 6
31 21 1
31 21 6
31 25 1
31 25 6
31 29 1
31 29 6
34 1 1
34 1 6
34 5 1
34 5 6
34 9 1
34 9 6
34 13 1
34 13 6
34 17 1
34 17 6
34 21 1
34 21 6
34 25 1
34 25 6
34 29 1
34 29 6
34 33 1
34 33 6
37 1 1
37 5 1
37 9 1
37 13 1
37 17 1
37 21 1
37 25 1
37 29 1
37 33 1
37 37 1
40 1 1
40 5 1
40 9 1
40 13 1
40 17 1
40 21 1
40 25 1
40 29 1
40 33 1
40 37 1

Expected output

Example 8

Input

60 5 17 23 11 1000003
240
1 1 1
60 1 1
60 60 1
60 30 1
1 1 2
59 1 2
59 59 2
59 30 2
1 1 3
58 1 3
58 58 3
58 29 3
1 1 4
57 1 4
57 57 4
57 29 4
1 1 5
56 1 5
56 56 5
56 28 5
1 1 6
55 1 6
55 55 6
55 28 6
1 1 7
54 1 7
54 54 7
54 27 7
1 1 8
53 1 8
53 53 8
53 27 8
1 1 9
52 1 9
52 52 9
52 26 9
1 1 10
51 1 10
51 51 10
51 26 10
1 1 11
50 1 11
50 50 11
50 25 11
1 1 12
49 1 12
49 49 12
49 25 12
1 1 13
48 1 13
48 48 13
48 24 13
1 1 14
47 1 14
47 47 14
47 24 14
1 1 15
46 1 15
46 46 15
46 23 15
1 1 16
45 1 16
45 45 16
45 23 16
1 1 17
44 1 17
44 44 17
44 22 17
1 1 18
43 1 18
43 43 18
43 22 18
1 1 19
42 1 19
42 42 19
42 21 19
1 1 20
41 1 20
41 41 20
41 21 20
1 1 21
40 1 21
40 40 21
40 20 21
1 1 22
39 1 22
39 39 22
39 20 22
1 1 23
38 1 23
38 38 23
38 19 23
1 1 24
37 1 24
37 37 24
37 19 24
1 1 25
36 1 25
36 36 25
36 18 25
1 1 26
35 1 26
35 35 26
35 18 26
1 1 27
34 1 27
34 34 27
34 17 27
1 1 28
33 1 28
33 33 28
33 17 28
1 1 29
32 1 29
32 32 29
32 16 29
1 1 30
31 1 30
31 31 30
31 16 30
1 1 31
30 1 31
30 30 31
30 15 31
1 1 32
29 1 32
29 29 32
29 15 32
1 1 33
28 1 33
28 28 33
28 14 33
1 1 34
27 1 34
27 27 34
27 14 34
1 1 35
26 1 35
26 26 35
26 13 35
1 1 36
25 1 36
25 25 36
25 13 36
1 1 37
24 1 37
24 24 37
24 12 37
1 1 38
23 1 38
23 23 38
23 12 38
1 1 39
22 1 39
22 22 39
22 11 39
1 1 40
21 1 40
21 21 40
21 11 40
1 1 41
20 1 41
20 20 41
20 10 41
1 1 42
19 1 42
19 19 42
19 10 42
1 1 43
18 1 43
18 18 43
18 9 43
1 1 44
17 1 44
17 17 44
17 9 44
1 1 45
16 1 45
16 16 45
16 8 45
1 1 46
15 1 46
15 15 46
15 8 46
1 1 47
14 1 47
14 14 47
14 7 47
1 1 48
13 1 48
13 13 48
13 7 48
1 1 49
12 1 49
12 12 49
12 6 49
1 1 50
11 1 50
11 11 50
11 6 50
1 1 51
10 1 51
10 10 51
10 5 51
1 1 52
9 1 52
9 9 52
9 5 52
1 1 53
8 1 53
8 8 53
8 4 53
1 1 54
7 1 54
7 7 54
7 4 54
1 1 55
6 1 55
6 6 55
6 3 55
1 1 56
5 1 56
5 5 56
5 3 56
1 1 57
4 1 57
4 4 57
4 2 57
1 1 58
3 1 58
3 3 58
3 2 58
1 1 59
2 1 59
2 2 59
2 1 59
1 1 60
1 1 60
1 1 60
1 1 60

Expected output