THPT Chuyên Bến Tre

Trong giờ học toán, Miticc cảm thấy rất chán nản với môn hình học,… Anh ta quyết định buông viết và làm 1 giấc, trong mơ Miticc đã gặp một chú bò, anh ta đã được chú bò giới thiệu một trò chơi hết sức thú vị.

Đầu tiên chú bò sẽ cho anh ta một bảng hình vuông có kích thước N*N ô, nhiệm vụ của Miticc là phải tính được diện tích của hình chữ nhật lớn nhất được tạo bởi các ô có phần tử là một số chính phương hoặc số đó là lập phương của một số nguyên tố.

Nhiệm vụ của Miticc là không quá khó khăn, và tất nhiên là anh ta làm được, trong lúc đang giải trò chơi của chú bò đưa ra, anh ta bị lũ bạn kế bên ghẹo phá, :’( chúng chụp hình dìm và đánh thức anh dậy, hù dọa sẽ đăng hình anh lên facebook :’( Anh ta rất bực bội vì đã bị lũ bạn trêu ghẹo, thêm vào đó là chưa kịp trả lời trò chơi của chú bò :’( Anh ta ấm ức rất nhiều.

Nhiệm vụ của bạn là hãy giúp anh ta giải trò chơi mà chú bò đưa ra, thật may mắn là anh ta vẫn còn chút kí ức về cái bảng mà chú bò đã đưa, Nhưng… chuyện không như là mơ… anh ta chỉ còn nhớ ở dòng thứ x nào đó trong bảng hình vuông sẽ tăng từ cột u đến cột v, k đơn vị. Và tất nhiên đầu tiên chiếc bảng phải bằng 0.

Bạn hãy giúp Miticc giải ra bài toán nhé.

Input

- dòng đầu tiên gồm 2 số N và M (N là kích thước ma trận hình vuông, M là số lượng truy vấn mà Miticc sẽ nói cho bạn biết). (N<=1000; M<=50000).

- M dòng tiếp theo là truy vấn có dạng Q(x,u,v,k);  (0<=K<=50000);

Với mỗi truy vấn có dạng Q(x,u,v,k) ta tăng k đơn vị cho các phần tử từ vị trí u đến vị trí v trên dòng x.

Lưu ý: test luôn đảm bảo mỗi phần tử trong bảng không vượt quá 2^32.

Output

- Gồm một dòng duy nhất là kết quả bài toán.

Example

 Input:

5 8
1 1 2 27
2 2 5 3
3 1 5 1
4 1 5 1
4 2 3 4912
4 5 5 9
5 1 4 1
5 1 1 1
Output:

9

giải thích: