피라미드

시간 제한4초메모리 제한512 MB

요약

선형 점화식으로 n줄 삼각뿔을 만들고, 아래 방향 삼각형 부분뿔 안의 최댓값을 묻는 질의에 답한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 배열, 구현
정답자: 아직 제출이 없습니다

문제

미르코와 슬라브코는 사막을 걷다가 피라미드를 발견했다. 문에 붙은 작은 콘솔에는 여섯 개의 정수 $n$ , $v$ , $a$ , $b$ , $c$ , $m$ 으로 된 수수께끼가 떠 있다. 이 수가 나타내는 피라미드를 만들어 콘솔에 입력해야 문이 열린다.

피라미드는 $n$ 개의 행으로 이루어진다. $i$ 번째 행에는 $i$ 개의 수 $p(i,1)$ , $p(i,2)$ , $\dots$ , $p(i,i)$ 가 놓이고, 각 값은 다음 규칙으로 정한다.

$p(1,1) = v$ . 이 값에는 나머지 연산을 하지 않으므로, $v \ge m$ 이어도 $p(1,1)$ 은 $v$ 그대로다.
$2 \le i \le n$ 일 때 $p(i,1) = (c \times p(i-1,1)) \bmod m$
$2 \le i \le n$ 이고 $2 \le j \le i$ 일 때 $p(i,j) = (a \times p(i,j-1) + b \times p(i-1,j-1)) \bmod m$

문이 열리면 콘솔이 질문 $q$ 개를 던진다. 각 질문은 세 정수 $r$ , $s$ , $x$ 로 주어지고, 꼭대기가 $p(r,s)$ 이고 한 변의 길이가 $x$ 인 부분 피라미드를 가리킨다. 이 부분 피라미드는 $r \le i \le r+x-1$ 과 $s \le j \le s+(i-r)$ 를 동시에 만족하는 칸 $p(i,j)$ 를 모두 모은 것이다. 예를 들어 $r=2$ , $s=2$ , $x=2$ 인 부분 피라미드는 $p(2,2)$ , $p(3,2)$ , $p(3,3)$ 세 칸으로 이루어지고, 그림에서 빨간색으로 칠한 부분이다. 질문마다 그 부분 피라미드에 들어 있는 수의 최댓값을 답해야 한다.

입력

첫째 줄에 여섯 정수 $n$ , $v$ , $a$ , $b$ , $c$ , $m$ 이 공백으로 구분되어 주어진다. ( $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$ )

둘째 줄에 질문의 개수 $q$ 가 주어진다. ( $1 \le q \le 5 \times 10^5$ )

이어지는 $q$ 개의 줄에 각각 세 정수 $r$ , $s$ , $x$ 가 주어진다. ( $1 \le r \le n$ , $1 \le s \le r$ , $1 \le x \le n-r+1$ )

출력

$q$ 개의 줄을 출력한다. $k$ 번째 줄에는 $k$ 번째 질문이 가리키는 부분 피라미드에 들어 있는 수의 최댓값을 출력한다.

예제8

예제 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

입력

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

예상 출력

예제 4
입력
```
1 1 1 1 1 2
1
1 1 1
```
예상 출력
```
1
```

예제 5

입력

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

예상 출력

1000000000
1000000000
0

예제 6

입력

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

예상 출력

예제 7

입력

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

예상 출력

예제 8

입력

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

예상 출력