17282번 - Grid Query 2

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

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

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

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

둘째줄부터 Q개의 줄에 다섯 개의 수 A_i, B_i, C_i, D_i, K_i가 주어진다. (0 ≤ A_i, B_i, C_i, D_i, K_i < 2³¹)

X_i1 = (A_i xor last_ans) mod 10⁵, Y_i1 = (B_i xor last_ans) mod 10⁵, X_i2 = (C_i xor last_ans) mod 10⁵, Y_i2 = (D_i xor last_ans) mod 10⁵, V_i = (K_i xor last_ans) mod (10⁹ + 7)이며 last_ans는 최초 0이고, 현재 시점에서 가장 마지막으로 출력한 값이다.

X_i1, Y_i1, X_i2, Y_i2는 i번째 쿼리의 X₁, Y₁, X₂, Y₂이고, 0 ≤ X_i1, Y_i1, X_i2, Y_i2 < 10⁵, 0 ≤ V_i < 10⁹ + 7, X_i1 ≤ X_i2, Y_i1 ≤ Y_i2를 만족한다.

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

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