31425번 - 토지 판매

문제

때는 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\limits_{i=a_l}^{c_l} \bigoplus\limits_{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+3$번째 줄에 $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$진법을 사용해야 함에 유의하여라.

제한

힌트