피라미드

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

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

1. $p(1,1) = v$. 이 값에는 나머지 연산을 하지 않으므로, $v \ge m$이어도 $p(1,1)$은 $v$ 그대로다.
2. $2 \le i \le n$일 때 $p(i,1) = (c \times p(i-1,1)) \bmod m$
3. $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$번째 질문이 가리키는 부분 피라미드에 들어 있는 수의 최댓값을 출력한다.