← 返回题目列表

Codeforces · 803/G

G. 周期性 RMQ 问题

中文机器翻译题面 查看原题

给定一个由正整数组成的数组 a 和对该数组的 q 个查询。有两种类型的查询:

- 1 l r x — 对于每个索引 i,使得 l ≤ i ≤ r 设置 ai = x。
- 2 l r — 找到满足 l ≤ i ≤ r 的 ai 中的最小值。

我们认为这个问题太简单了。因此数组 a 以压缩形式给出:输入中有一个由 n 个元素和数字 k 组成的数组 b,并且在所有查询之前 a 等于 k ​​个数组 b 的串联(因此 a 的大小为 n·k)。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 104)。

第二行包含 n 个整数 — 数组 b 的元素 (1 ≤ bi ≤ 109)。

第三行包含一个整数 q (1 ≤ q ≤ 105)。

接下来是 q 行,每行代表一个查询。每个查询被指定为 1 l r x — 将从 l 到 r 的段中的所有元素(包括边界)设置为 x (1 ≤ l ≤ r ≤ n·k, 1 ≤ x ≤ 109) 或 2 l r — 找到从 l 到 r 的段中的所有元素 (1 ≤ l ≤ r ≤ n·k) 中的最小值。

输出

对于类型 2 的每个查询,打印该查询的答案 — 相应段上的最小值。

示例

输入 #1

3 1
1 2 3
3
2 1 3
1 1 2 4
2 1 3

输出 #1

1
3

输入 #2

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

输出 #2

1
5
1