題目描述

傳聞 Kinda 有一種顏料，可以令白色的圖層變黑，也可以令黑色的圖層變白。

小紀出於好奇心，把這種顏料買了回來。他在一張 𝑁 × 𝑁 𝑐𝑚 的空白畫紙上當成了 𝑁 × 𝑁 的表格，這個表格中每個格均被等分為1 × 1 𝑐𝑚²。

接下來，小紀進行了 𝑇 次操作。每次操作時，他會把隨機一個子表格全部塗上顏料。

𝑇 次操作完成後，小紀希望知道剩下黑色部分的面積是多少 𝑐𝑚²。

身為他唯一的秘書，你被要求計算這個面積。

輸入格式

第一行兩個正整數 𝑁, 𝑇，以空格分隔。

接下來 𝑇 行，每行四個正整數 𝑥, 𝑦, 𝑥₁, 𝑦₁，以空格分隔。其中，

𝑥, 𝑦 表示小紀填色的矩陣左上角的那個格在第 𝑥 行第 𝑦 列；

𝑥₁, 𝑦₁ 則表示矩陣右下角的那個格在第 𝑥₁ 行第 𝑦₁ 列。

保證 𝑥 ≤ 𝑥₁ ≤ 𝑁, 𝑦 ≤ 𝑦₁ ≤ 𝑁。

輸出格式

畫紙上黑色部分的總面積。

Samples

["5 2 \r\n2 2 3 4 \r\n1 3 3 4","9 1 \r\n1 1 9 9"]

["4","81"]

提示

數據範圍

[10 分, 1.0𝑠] 測試數據 1~10: 𝑁 ≤ 500, 𝑇 ≤ 100。

[10 分, 1.0𝑠] 測試數據 11~15: 𝑁, 𝑇 ≤ 10³。

[15 分, 1.0𝑠] 測試數據 16~20: 𝑁 ≤ 10³, 𝑇 ≤ 10⁶。

原始資料

• Zero1 題號：b292
• Hydro 題號：Z1292
• Locale：zh_TW
• Display：practice