題目描述

小紀正在努力為一個白色正方形畫紙填色，然而他面臨着一個嚴重的問題：他手頭上沒有任何顏料。更糟糕的是，他所在的城市竟然沒有一家售賣顏料的商店。於是，他決定找小峯幫忙。 小峯知道 Kinda 家裏藏了一瓶「傳奇」的透明顏料，又聽說 Kinda 連人帶貓去了火星與外星人友善交流，於是他偷偷地到了 Kinda 家尋找這個顏料。 小峯駕駛著他那輛「傳奇」的跑車，在馬路上瘋狂狂奔，速率高達 400 km/h，結果引發了一連串的事故。過了大約 3 個小時，他終於抵達了 Kinda 家。 Kinda 家位於市郊，總面積約為 300 英畝。這是小峯第一次來到 Kinda 家，Kinda 家分為 8 座大樓，有其中 4 座是全給貓住的。 傳聞，Kinda 養的貓有劇毒，正常人被咬一口會在 5 秒內致死。但事實上，Kinda 已經把他所有的貓都帶去火星了。所以，小峯放心地進去了展開他的搜索工作。 小峯不間斷地搜索了 168 個小時後，還未找到那個顏料。這時，他 突然在貓窩中不小心踩到了一個按鈕。一扇大門自動地打開了，小峯順着樓梯地到了地下室。在那裏，小峯眼前發亮了。在他眼前，是無數在發光的金銀珠寶。那裏有一個巨大的寶箱，他順手打開了，裏面正是他要找的東西。 他高興地帶走了，出去前還不忘把門關掉。 同時，小峯帶走顏料的警報訊號從地球傳給了在火星的 Kinda，他不禁喊道：「大膽『小瘋』，竟敢擅自拿取我顏料？回地球後，看我怎樣治你！」小峯突然得知了 Kinda 會在一天內返回地球 (是 Kinda 搞的鬼)，心裏十分焦急。於是他把跑車開到 600 km/h，回來的途中不僅引發了好幾場大火和爆炸事件，還***(黃皓紀要求刪除的)。 總算，小峯回到小紀家了，把顏料交給了小紀。而他們倆必須在 Kinda 回家前，完成填色，並把顏料放回原位。否則，他們將被 Kinda 和外星人們精心訓練的貓擊殺。但是，他們倆並不知道，Kinda 已經知道了他們偷顏料的事實。經過試驗後，小峯和小紀驚訝地發現，當 Kinda 的顏料塗上白色的圖層時，會變成黑色；塗上黑色的圖層時，會變成白色。 由於 Kinda 快回地球了，小紀實在是太急，於是在白色的正方形畫紙上一直亂塗矩形。 就這樣過了好幾個小時，作品終於完成了。那個正方形雖然是亂畫的，但很像現代藝術。 而剛好，Kinda 從火星回到地球了。他生氣地帶着他的殺手貓找上門來。但看到這份傑作後，整個人的殺心都消失了。最後，小峯始終要負上偷顏料的代價，於是把畫作送給了 Kinda (得不死)。 Kinda 回到家後，想統計一下這個巨大畫紙黑色部分佔的面積，他清楚知道小紀每次畫的矩形的左上角和右下角的坐標。現在給定這些數據，你能幫助 Kinda 計算出畫紙上黑色部分的總面積嗎？

輸入格式

第一行兩個正整數 𝑁, 𝑇，分別表示正方形的邊長和填色的次數，以空格分隔。

接下來 𝑇 行，每行四個正整數 𝑋, 𝑌,𝑋₁, 𝑌₁(𝑋, 𝑌, 𝑋₁, 𝑌₁ ≤ 𝑁)，以空格 分隔。

其中，𝑋, 𝑌 表示小紀填色的矩陣左上角的那個格在第 𝑋 行 第 𝑌 欄；

𝑋₁, 𝑌₁ 則表示矩陣右下角的那個格在第 𝑋₁ 行第 𝑌₁ 欄。 保證 𝑋 ≤ 𝑋₁，𝑌 ≤ 𝑌₁。

輸出格式

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

Samples

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

["4","81"]

提示

測試數據 1~5: 𝑁, 𝑇 ≤ 100。

測試數據 6~10: 𝑁 ≤ 100, 𝑇 ≤ 10³。

測試數據 11~15: 𝑁, 𝑇 ≤ 10³。

測試數據 16~18: 𝑁 ≤ 10³ , 𝑇 ≤ 5 × 10⁴。

測試數據 19~20: 𝑁 ≤ 10³ , 𝑇 ≤ 10⁶。

原始資料

• Zero1 題號：b211
• Hydro 題號：Z1211
• Locale：zh_TW
• Display：practice