#105. 文艺平衡树

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

这是一道模板题。

您需要写一种数据结构(可参考题目标题),来维护一个序列,其中需要提供以下操作:

翻转一个区间,例如原有序序列是 5 4 3 2 1,翻转区间是 [2,4] [2, 4] [2,4] 的话,结果是 5 2 3 4 1

输入格式

第一行为 n,m n, m n,mn n n 表示初始序列有 n n n 个数,这个序列依次是 {1,2,…n−1,n} \{ 1, 2, \ldots n - 1, n \} {1,2,n1,n}m m m 表示翻转操作次数。
接下来 m m m 行每行两个数 [l,r] [l, r] [l,r],数据保证 1≤l≤r≤n 1 \leq l \leq r \leq n 1lrn

输出格式

输出一行 n n n 个数字,表示原始序列经过 m m m 次变换后的结果。

样例

样例输入

5 3
1 3
1 3
1 4

样例输出

4 3 2 1 5

数据范围与提示

1≤n,m≤105 1 \leq n, m \leq 10 ^ 5 1n,m105