Whiteking sắp tham gia một trò chơi trang trí địa phương. Khu vực anh ấy muốn trang trí có dạng lưới $N \times N$, trong đó lưới đơn vị được biểu diễn bởi các ô vuông $1 \times 1$, tọa độ của ô ở góc trên bên trái là $(1, 1)$ và tọa độ của ô ở góc dưới bên phải là $(N, N)$. Do đó, tọa độ của ô tham chiếu đến tọa độ góc dưới bên phải của ô đó. Từ đây, có thể thấy ô nằm tại $(x, y)$ chiếm một diện tích hình vuông tương ứng với $[x - 1, x] \times [y - 1, y]$. Mỗi ô có giá trị thẩm mỹ riêng, ban đầu tất cả các ô đều có giá trị thẩm mỹ bằng 0.

Trò chơi trang trí địa phương là một trò chơi mà người chơi kiếm điểm bằng cách sử dụng ba hành động sau đây:

• Chia lưới thành các vùng khác nhau bằng cách vẽ một đường thẳng theo chiều ngang hoặc chiều dọc. Ban đầu, chỉ có một vùng duy nhất kích thước $N \times N$. Các đường thẳng kéo dài vô tận theo cả hai hướng: ví dụ, nếu bạn vẽ một đường thẳng theo chiều ngang và một đường thẳng theo chiều dọc, vùng ban đầu sẽ được chia thành tổng cộng bốn vùng.
• Chọn một ô và trang trí vùng mà nó thuộc về. Kết quả là, giá trị thẩm mỹ của tất cả các ô trong vùng được trang trí sẽ tăng thêm một giá trị cho trước.
• Chọn một hình chữ nhật trên lưới và kiếm số điểm bằng với giá trị thẩm mỹ của ô đẹp nhất trong hình chữ nhật đó.

Whiteking muốn biết trước anh ấy sẽ kiếm được bao nhiêu điểm cho mỗi hành động loại thứ ba. Vì vậy, anh ấy sẽ cho bạn xem một danh sách các hành động theo thứ tự mà anh ấy dự định thực hiện. Các hành động sẽ được đưa ra theo định dạng sau:

• “1 a b”: Nếu $a$ là 0, vẽ đường thẳng $x = b$, và nếu $a$ là 1, vẽ đường thẳng $y = b$.
• “2 a b X”: Chọn ô nằm tại $(a, b)$, trang trí vùng mà nó thuộc về, làm tăng giá trị thẩm mỹ của tất cả các ô trong vùng đó thêm $X$.
• “3 a b c d”: Chọn một hình chữ nhật với $(a, b)$ là ô góc trên bên trái và $(c, d)$ là ô góc dưới bên phải, và kiếm số điểm bằng với giá trị thẩm mỹ của ô đẹp nhất trong đó.

Hãy giúp Whiteking tìm ra số điểm cho mỗi hành động loại thứ ba.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$).

Mỗi dòng trong số $Q$ dòng tiếp theo mô tả một hành động theo định dạng được nêu trong mô tả bài toán.

Đối với hành động loại 1, $0 \le a \le 1$ và $1 \le b \le N - 1$.

Đối với hành động loại 2, $1 \le a, b \le N$ và $-10^9 \le X \le 10^9$.

Đối với hành động loại 3, $1 \le a \le c \le N$ và $1 \le b \le d \le N$.

Có tối đa 25 000 hành động loại 2, và ít nhất 1 hành động loại 3.

Dữ liệu ra

Đối với mỗi hành động loại thứ ba, in ra số điểm mà Whiteking sẽ nhận được cho hành động đó.

Ví dụ

Dữ liệu vào 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

Dữ liệu ra 1

0
-3
-3
1