DS 팀 선발전

제34회 국제 데이터 구조 올림피아드(International Olympiad in Data Structures)가 곧 열린다. 출전하려면 각국의 팀 선발전을 통과해야 한다. Cat 팀의 일원으로서 Cat 팀 선발전에서 이 문제를 풀어야 한다.

무한한 평면 위에 정수 좌표를 갖는 점이 무한히 많이 있으며, 각 점은 $(x, y)$로 나타낼 수 있다. 처음에는 모든 점의 가중치가 $0$이다. 다음 형식의 연산을 $q$번 수행해야 한다.

• 1 $x$ $y$ $d$ $w$: $|X-x| < d$이고 $|Y-y| < d$를 만족하는 모든 점 $(X,Y)$의 가중치를 $w \cdot (d - \max(|X-x|,|Y-y|))$만큼 증가시킨다.
• 2 $x_1$ $x_2$ $y_1$ $y_2$: $x_1 \le x \le x_2$이고 $y_1 \le y \le y_2$를 만족하는 점 $(x,y)$의 가중치 합을 출력한다. 합이 클 수 있으므로 $2^{30}$으로 나눈 나머지를 출력한다.

첫 줄에 연산의 개수 $m$ ($1 \le m \le 10^5$)이 주어진다.

이어지는 $m$개의 줄에는 다음 형식 중 하나로 정수들이 주어진다.

• 1 $x$ $y$ $d$ $w$ ($1 \le x,y,d,w \le 10^8$)
• 2 $x_1$ $x_2$ $y_1$ $y_2$ ($1 \le x_1 \le x_2 \le 10^8$, $1 \le y_1 \le y_2 \le 10^8$)

형식 2 연산마다 구한 가중치 합을 한 줄에 하나씩 출력한다. 값은 $2^{30}$으로 나눈 나머지이다.