该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

翁老师管理着一个果园，一排种植了 $N$ 棵果树。每棵树的编号从 $1$ 到 $N$ ，其中 $i$ 棵树结了 $A_i$ 个果实。

这个果园里的果树有一个神秘的特性：无论收获多少次，果实的数量都不会减少。

每棵树的收获点 $P_i$ 最初为 $0$ 。当一棵树被采收一次后，树上的果实数量就会被加到它的采收点数上。例如，如果一棵结有 $5$ 果实的树被采收了 $3$ 次，它的收获点数就会变成 $5 \times 3 = 15$ 。

收获季节已经到来，翁老师将在 $M$ 天内进行收获。

• 在第 $j$ 天，他将从编号为 $L_j$ 到 $R_j$ 的每棵树（树 $L_j, L_j + 1, \ldots, R_j$ ）上收获一次。

全部采收结束后，确定每棵树的采收点 $P_1, P_2, \ldots, P_N$ 。

输入格式

第一行两个整数 $N$ 和 $M$。（$1\leq N,M\le 2\times 10^5$）

第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。（$1\leq A_i\le 10^9$）

接下来 $M$ 行，每行输入两个整数 $L_i,R_i$。（$1\leq L_i\le R_i\le N$）

输出格式

输出一行 $N$ 个空格隔开的整数分别代表每棵树上的采收值。

5 3
3 1 4 1 5
1 3
2 4
3 5

3 2 12 2 5

7 5
10 20 30 40 50 60 70
1 7
2 5
3 3
1 4
5 7

20 60 120 120 150 120 140

10 8
100 200 300 400 500 600 700 800 900 1000
1 5
3 8
6 10
2 4
1 10
5 5
7 9
1 3

300 800 1500 1600 2000 1800 2800 3200 2700 2000