出處: 2020 NPSC網際網路程式設計大賽高中組初賽pG

這天，一款全新的妹妹虛擬實境遊戲即將發售，身為這類遊戲的愛好者——小 Y 為了搶先體驗，他現在身處在一個很長的隊伍中，漫長的等待時間使他非常無聊，所以他決定開始觀察隊伍的排隊現象。

小 Y 觀察到隊伍內總共有 \(N\) 個人，一開始隊伍是在筆直的數線上的，第 \(i\) 個人的座標為 \(i\)。小 Y 也知道自己是這隻隊伍的第 \(Q+1\) 個人，所以他很在意前 \(Q\) 個人依序買到遊戲後，隊伍會發生什麼事。

因此，小 Y 接下來會觀察 \(Q\) 次事件，第 \(i\) 次事件排在隊伍最前面的人，也就是第 \(i\) 個人，就會買到遊戲，並離開隊伍，自此這個人的位置便會出現空格，此時隊伍可能會開始移動。

不過常常會有討厭的人待在原地不動（像是滑手機之類的），導致後面的人會因為察覺不到隊伍有移動而無法前進，小 Y 發現對於第 \(i\) 次事件，有往前移動的人是還待在原隊伍的前 \(k_i\) 位（也就是第 \(i+1\sim i+k_i\) 個人），這 \(k_i\) 位會不受影響地依序直接移動到前 \(k_i\) 個位置，也就是座標 \(1\sim k_i\)。

小 Y 已經把所有事件的 \(k_i\) 都紀錄下來了，你可以告訴他，對於每次事件，隊伍內所有人（包含該次事件買到遊戲的人）移動的距離總和是多少呢？當然，我們假設每次事件只有買到遊戲的人和待在原隊伍的前 \(k_i\) 個人會做移動，且任何人都只會在事件發生時移動。

輸入格式

輸入的第一行有兩個正整數 \(N,Q\)，代表隊伍的人數、小 Y 前面排了多少人。

第二行有 \(Q\) 個以空格分開的整數 \(k_1, k_2, \cdots, k_Q\)，代表每次事件，往前移動的人是還待在原隊伍的前 \(k_i\) 位，若 \(k_i=0\) 代表此次事件除了買遊戲的人以外，沒有其他的人移動。

• \(1 \le N \le 10^9\)
• \(1 \le Q \le \min(N-1,10^6)\)
• \(0 \le k_i\le N-i\)

輸出格式

輸出只有一行 \(Q\) 個數字 \(d_1,d_2,\cdots,d_Q\)，代表第 \(i\) 次事件中，所有人移動的距離總和是 \(d_i\)。數字之間以單一空格隔開，最後一個數字後面必須是一個單一的換行字元。

範例輸入1

10 5
3 4 2 5 3

範例輸出1

3 6 2 15 3

範例輸入2

8 6
3 1 2 1 0 0

範例輸出2

3 1 5 1 0 5

範例輸入3

1000000000 7
100 1000 10000 8787 888777 98765 123456

範例輸出3

100 1901 28002 8787 4405105 98765 148148