#3013. 「模板」可持久化线段树

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

题目描述

给定长度为 的整数序列 ,下标为

现在要执行 次操作,其中第 次操作为给出三个整数 ,求 (即 的下标区间 )中第 小的数是多少。

输入格式

第一行包含两个整数

第二行包含 个整数,表示整数序列

接下来 行,每行包含三个整数 ,用以描述第 次操作。

输出格式

对于每次操作输出一个结果,表示在该次操作中,第 小的数的数值。

每个结果占一行。

样例

样例输入

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

样例输出

5
6
3

数据范围与提示

  • 对于 的数据,满足
  • 对于 的数据,满足
  • 对于 的数据,满足
  • 对于 的数据,满足