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

题目描述

某实验室发现了一种特殊的能量序列 $E$，定义如下：

• $E_1=1$；
• $E_2=2$；
• 对于 $n \ge 3$，有 $E_n=(E_{n-1}+2 \times E_{n-2}) \bmod 1000$。

在生成出前 $N$ 项后，研究员还会对它进行 $Q$ 次“局部优化”。每次给定一个区间 $[L,R]$，都要把当前序列中这个区间内的元素按升序排序。

注意，所有操作都必须在上一次操作后的序列基础上继续进行。

请输出全部 $Q$ 次操作结束后的完整序列。

输入格式

第一行两个整数 $N,Q$。

接下来 $Q$ 行，每行两个整数 $L,R$，表示一次排序区间。

输出格式

输出一行 $N$ 个整数，表示最终序列。

12 1
9 12

1 2 4 8 16 32 64 128 24 48 256 512

12 2
9 12
7 10

1 2 4 8 16 32 24 48 64 128 256 512

说明/提示

样例 1 解释：

原序列前 $12$ 项为：1 2 4 8 16 32 64 128 256 512 24 48。对区间 $[9,12]$ 排序后，区间中的 256 512 24 48 变为 24 48 256 512，因此得到样例输出。

样例 2 解释：

先按样例 1 的方式处理区间 $[9,12]$，再对新区间 $[7,10]$ 中的 64 128 24 48 进行升序排序，得到 24 48 64 128，最终序列即为样例输出。

对于所有测试点，保证 $1 \le N,Q \le 100$，$1 \le L \le R \le N$。