区间平方根操作

题目描述

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

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

[ a[i] = \lfloor \sqrt{a[i]} \rfloor ]

其中 ( \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 1 \times 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