시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 1024 MB 32 15 2 100.000%

문제

세로 100000, 가로 100000 크기의 값이 전부 0으로 채워진 2차원 배열이 있다. 이 배열에서 행 번호는 아래로 갈 수록, 열 번호는 오른쪽으로 갈 수록 증가한다. i번째 행, j번째 열에 해당되는 위치는 (i-1,j-1)로 표현한다.

Lawali는 여러분이 더욱 고통받는 모습을 보기 위해 Q번 다음과 같은 연산을 하려고 한다.

  1. X1 Y1 X2 Y2 V : (X1,Y1) 와 (X2,Y2)사이의 모든 위치에 해당되는 값에 V를 더하는 업데이트 연산을 한다. (V > 0)
  2. X1 Y1 X2 Y2 0 : (X1,Y1) 와 (X2,Y2) 사이의 모든 위치에 해당되는 값의 합을 구하는 쿼리를 수행하고 출력한다.

입력

첫째줄에 Q가 주어진다 (1 ≤ Q ≤ 2.5×105)

둘째줄부터 Q개의 줄에 다섯 개의 수 Ai, Bi, Ci, Di, Ki가 주어진다. (0 ≤ Ai, Bi, Ci, Di, Ki < 231)

Xi1 = (Ai xor last_ans) mod 105, Yi1 = (Bi xor last_ans) mod 105, Xi2 = (Ci xor last_ans) mod 105, Yi2 = (Di xor last_ans) mod 105, Vi = (Ki xor last_ans) mod (109 + 7)이며 last_ans는 최초 0이고, 현재 시점에서 가장 마지막으로 출력한 값이다.

Xi1, Yi1, Xi2, Yi2는 i번째 쿼리의 X1, Y1, X2, Y2이고, 0 ≤ Xi1, Yi1, Xi2, Yi2 < 105, 0 ≤ Vi < 109 + 7, Xi1 ≤ Xi2, Yi1 ≤ Yi2를 만족한다.

1번 쿼리는 50000개를 넘지 않으며 2번 쿼리는 1개 이상 있다.

출력

각 줄에 2번 쿼리의 결과 mod (10+ 7)을 출력한다.

예제 입력 1

10
40 31 99 46 987780775
38 0 68 74 0
330276393 330276413 330276477 330276459 822003462
330276378 330276364 330276464 330276479 306736652
330276394 330276452 330276459 330276424 496257100
330276368 330276474 330276459 330276474 520765327
330276412 330276411 330276372 330276460 330276394
969279116 969279132 969279133 969279209 969279141
80818941 80818932 80818860 80818880 555081578
80818880 80818869 80818848 80818840 80818939

예제 출력 1

330276394
969279141
80818939
775484641

출처

  • 문제를 만든 사람: Lawali

채점

  • 이 문제의 채점 우선 순위는 다른 문제보다 낮다.