Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MTHCN - Hình chữ nhật kì lạ

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mthcn


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:

Được gửi lên bởi:Đặng Minh Tiến
Ngày:2014-09-17
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC MAWK BC C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D DART ELIXIR FANTOM FORTH GRV JULIA KTLN LUA NODEJS OBJC OCAML OCT PAS-FPC PIKE PROLOG PYPY3 R RACKET CHICKEN ST SQLITE SWIFT UNLAMBDA
Nguồn bài:CBHT

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.