격자 쿼리 2

세로 $10^5$, 가로 $10^5$ 크기의 2차원 배열이 있고, 모든 값은 처음에 0으로 채워져 있다. 행 번호는 아래로 갈수록, 열 번호는 오른쪽으로 갈수록 커진다. $i$번째 행, $j$번째 열의 위치는 $(i-1,j-1)$로 표현한다.

Lawali는 여러분이 더욱 고통받는 모습을 보기 위해 $Q$번 다음 두 종류의 연산을 하려고 한다.

1. $X_1$ $Y_1$ $X_2$ $Y_2$ $V$: $(X_1,Y_1)$와 $(X_2,Y_2)$ 사이의 모든 위치에 해당하는 값에 $V$를 더한다. ($V > 0$)
2. $X_1$ $Y_1$ $X_2$ $Y_2$ $0$: $(X_1,Y_1)$와 $(X_2,Y_2)$ 사이의 모든 위치에 해당하는 값의 합을 구하고 출력한다.

첫째 줄에 $Q$가 주어진다. ($1 \le Q \le 2.5 \times 10^5$)

둘째 줄부터 $Q$개의 줄에 다섯 개의 정수 $A_i, B_i, C_i, D_i, K_i$가 주어진다. ($0 \le A_i, B_i, C_i, D_i, K_i < 2^{31}$)

last_ans는 처음에 0이고, 가장 최근에 출력한 값이다. $i$번째 쿼리의 값은 다음과 같이 정한다.

$X_{i1} = (A_i \oplus \text{last\_ans}) \bmod 10^5$, $Y_{i1} = (B_i \oplus \text{last\_ans}) \bmod 10^5$, $X_{i2} = (C_i \oplus \text{last\_ans}) \bmod 10^5$, $Y_{i2} = (D_i \oplus \text{last\_ans}) \bmod 10^5$, $V_i = (K_i \oplus \text{last\_ans}) \bmod (10^9+7)$

$X_{i1}, Y_{i1}, X_{i2}, Y_{i2}$는 $i$번째 쿼리의 $X_1, Y_1, X_2, Y_2$이며, $0 \le X_{i1}, Y_{i1}, X_{i2}, Y_{i2} < 10^5$, $0 \le V_i < 10^9+7$, $X_{i1} \le X_{i2}$, $Y_{i1} \le Y_{i2}$를 만족한다.

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

2번 쿼리마다 합을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.