题目描述

有 $n$ 个羊圈排成一排，第 $i$ 个羊圈中有 $a_i$ 只羊。你有 $m$ 个神奇口袋，第 $j$ 个口袋的容量是 $b_j$。

向某个羊圈扔出一个口袋后，它会从这个羊圈以及与它相邻的羊圈中，各套走 $x$ 只羊，其中 $x$ 为当前口袋的容量。

现在记录下你每次把口袋扔向哪个羊圈，求：最终每个羊圈中剩余的羊的数量。

输入格式

第一行：两个整数 $n,m$，分别表示羊圈的数量和口袋的数量。

第二行：$n$ 个整数 $a_1,a_2...a_n$，分别表示初始时每个羊圈中羊的数量。

此后 $m$ 行：每行两个整数，表示你每次把口袋扔向第几个羊圈，以及该口袋的容量。

输出格式

$n$ 个整数，分别表示最终每个羊圈中羊的数量，以空格分隔。

样例

5 2
20 30 40 50 60
3 10
5 45

20 20 30 0 15

样例 $1$ 解释

第一个口袋扔向第 $3$ 个羊圈，容量是 $10$。每个羊圈的数量变为 $20,20,30,40,60$。

第二个口袋扔向第 $5$ 个羊圈，容量是 $45$。每个羊圈的数量变为 $20,20,30,0,15$。

数据范围

对于所有数据，$1≤n,m,a_i,b_j≤100$。