cho.sh

벽에 붙은 포스터

서로 겹치지 않는 최대 50000개의 축에 나란한 직사각형이 주어질 때, 질의 직사각형 내부에 들어가는 직사각형 넓이의 합을 온라인으로 구한다. 각 질의 좌표는 이전 답으로 복호화된다.

어려움8세그먼트 트리정렬이분 탐색누적 합아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

비밀 기지의 벽에는 직사각형 포스터가 여러 장 붙어 있다. 포스터는 구하기 어려운 물건이라 서로 겹치지 않게 붙인다.

가끔 벽에 붙일 만한 새 포스터가 도착하면 관리자는 그 포스터를 어디에 붙일지 정해야 한다. 이 과정의 한 단계를 맡아서, 후보 위치에 새 포스터를 붙였을 때 이미 붙어 있는 포스터가 가려지는 넓이의 합을 빠르게 계산하는 프로그램을 작성하시오.

평면에 서로 겹치지 않는 회색 직사각형 nn개가 있다. 질의 qq개가 주어지며, 각 질의는 직사각형 하나를 주고 그 안에 있는 회색 넓이의 합을 묻는다. 질의는 평면을 바꾸지 않는다.

질의는 온라인으로 처리해야 한다. 각 질의의 좌표가 직전 질의의 답으로 인코딩되어 있어서, 첫 질의에 답하기 전에 모든 질의를 미리 읽을 수 없다.

입력

첫째 줄에 정수 다섯 개 rr, cc, nn, qq, mm이 주어진다. (1≤r,c<m≤109+91 \leq r, c < m \leq 10^9 + 9, 0≤n,q≤50 0000 \leq n, q \leq 50\,000) 차례대로 벽의 높이, 벽의 너비, 벽에 붙어 있는 포스터의 수, 질의의 수, 질의를 인코딩하는 데 쓰는 법이다.

다음 nn개 줄에는 정수 네 개 x1,y1,x2,y2x_1, y_1, x_2, y_2가 주어진다. (0≤x1,x2≤r0 \leq x_1, x_2 \leq r, 0≤y1,y2≤c0 \leq y_1, y_2 \leq c) 포스터 한 장의 마주 보는 두 꼭짓점이다.

마지막 qq개 줄에는 정수 다섯 개 x1′,y1′,x2′,y2′,vx_1', y_1', x_2', y_2', v가 주어지며, 각 값은 00 이상 m−1m - 1 이하이다. 직전 질의의 답을 ll이라고 하자. 첫 질의에서는 l=0l = 0이다. 실제 좌표는 아래 식으로 구한다.

xi=(xi′+l⋅v)(modm)x_i = (x_i' + l \cdot v) \pmod m

yi=(yi′+l⋅v)(modm)y_i = (y_i' + l \cdot v) \pmod m

디코딩한 x1,y1,x2,y2x_1, y_1, x_2, y_2는 질의 직사각형의 마주 보는 두 꼭짓점이고, 0≤x1,x2≤r0 \leq x_1, x_2 \leq r과 0≤y1,y2≤c0 \leq y_1, y_2 \leq c를 만족한다.

모든 질의에서 vv가 00인 입력도 있다. 그런 입력에서는 인코딩이 좌표를 바꾸지 않는다.

출력

각 질의마다 한 줄에 정수 하나를 출력한다. 질의 직사각형 안에 있는 회색 넓이의 합이다.

힌트

아래 그림은 첫 번째 예제의 평면 전체이다.

두 번째 예제는 첫 번째 예제와 같은 질의 네 개를 00이 아닌 vv로 인코딩한 것이다. 디코딩하면 두 예제의 질의가 같고, 답도 같다.