토지 판매

때는 3022년이다. 옛날 국렬이와 지환이가 산 작은 땅은 1000년의 세월을 거쳐 $N$행 $M$열의 거대한 격자 모양 땅으로 커졌다. 이를 물려받은 후손 도훈이는 땅을 관리하기 버거워져 $B$ 나라 사람들에게 땅을 팔기로 했다.

$B$ 나라에서는 모든 수를 $B$진법으로 표기한다. 또한 두 수를 더할 때 일반적인 덧셈과 다른 방식으로 계산한다. 두 $B$진법 수 $X$와 $Y$를 더할 때, 각 자리의 합이 $B$ 이상이어도 자리올림을 하지 않고 나머지만 쓴다. $X$의 $t$번째 자리 수를 $x_t$, $Y$의 $t$번째 자리 수를 $y_t$라 하면, $Z = X + Y$의 $t$번째 자리 수는 $z_t = (x_t + y_t) \bmod B$이다. 이 받아올림 없는 $B$진수 덧셈을 기호 $\oplus$로 나타내자.

땅을 팔 때 고객과의 원활한 소통이 필수이므로, 도훈이도 땅의 가치를 매길 때 이 수 체계를 그대로 쓰려 한다. 넓은 땅의 칸마다 가치를 하나씩 정하기는 어렵다. 그래서 도훈이는 정수 $p, q, r, s$를 정하고, $i$행 $j$열 칸의 가치 $A_{ij}$를 $(p \times i + q) \oplus (r \times j + s)$로 정했다. 여기서 $\times$와 $+$는 일반적인 정수의 곱셈과 덧셈이다.

칸의 가치가 정해지면 고객 $K$명이 찾아온다. $l$번째 고객은 $[a_l, c_l] \times [b_l, d_l]$에 해당하는 직사각형 영역의 땅을 모두 사고 싶어 하며, 이때 땅의 가치는 $\bigoplus_{i=a_l}^{c_l} \bigoplus_{j=b_l}^{d_l} A_{ij}$이다. 각 질문에 대한 답을 계산하자. 답은 $B$진법으로 표기해야 한다.

첫 번째 줄에 세 정수 $N$, $M$, $B$가 공백으로 구분되어 주어진다. $N$, $M$은 격자의 크기이고, $B$는 사용하는 진법이다. ($1 \le N, M \le 10^{15}$, $2 \le B \le 10$)

두 번째 줄에 정수 $p, q, r, s$가 공백으로 구분되어 주어진다. ($1 \le p, r \le 10^{15}$, $0 \le q, s \le 10^{15}$, $p \times N, r \times M \le 10^{15}$)

세 번째 줄에 고객의 수 $K$가 주어진다. ($1 \le K \le 20\,000$)

네 번째 줄부터 $K$개의 줄에 걸쳐 $l$번째 고객의 질문을 나타내는 정수 네 개 $a_l$, $b_l$, $c_l$, $d_l$이 공백으로 구분되어 주어진다. ($1 \le a_l \le c_l \le N$, $1 \le b_l \le d_l \le M$)

각 질문에 대한 답을 질문 순서대로 $K$개의 줄에 출력한다. 불필요한 0은 출력해서는 안 된다. 즉, 답이 0이면 0으로 출력하고, 0이 아닌 수는 0으로 시작하면 안 된다. 모든 답은 $B$진법으로 출력해야 한다.