给定一个循环数组 a0, a1, ..., an - 1。它有两种类型的运算:
- inc(lf, rg, v) — 此操作将段 [lf, rg] 上的每个元素(包含)增加 v;
- rmq(lf, rg) — 此操作返回段 [lf, rg] 上的最小值(包含)。
假设线段是循环的,因此如果n = 5且lf = 3,rg = 1,则表示索引序列:3,4,0,1。
编写程序来处理给定的操作序列。
输入
第一行包含整数 n (1 ≤ n ≤ 200000)。下一行包含数组的初始状态:a0, a1, ..., an - 1 (- 106 ≤ ai ≤ 106), ai 是整数。第三行包含整数 m (0 ≤ m ≤ 200000),m — 操作数。接下来的 m 行每行包含一个操作。如果 line 包含两个整数 lf, rg (0 ≤ lf, rg ≤ n - 1) 则表示 rmq 运算,包含三个整数 lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — inc 运算。
输出
对于每个 rmq 操作,为其写入结果。请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。
示例
输入 #1
4 1 2 3 4 4 3 0 3 0 -1 0 1 2 1
输出 #1
1 0 0