区间平方根操作

题目描述

给定一个长度为 $n$ 的整数数组 $a$，以及 $q$ 次区间操作。

每次操作给定一个区间 $[l,r]$，需要对所有满足 $l \le i \le r$ 的下标 $i$ 执行如下更新：

其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。

请在依次执行完所有 $q$ 次操作后，输出最终的数组 $a$。

输入格式

• 第一行包含两个整数 $n, q$，分别表示数组长度和操作次数。
• 第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示初始数组。
• 接下来 $q$ 行，每行包含两个整数 $l, r$，表示一次区间操作。

输出格式

输出一行，包含 $n$ 个整数，表示所有操作完成后的数组。相邻整数之间用一个空格分隔。

数据范围

• $1 \le n \le 5 \times 10^5$
• $1 \le q \le 10^5$
• $0 \le a_i \le 10^{12}$
• $1 \le l \le r \le n$

样例

样例

输入

5 3
3 1 9 8 6
1 3
2 5
4 4

输出

1 1 1 1 2