# Codeforces 803G. Periodic RMQ Problem（动态开点线段树+ST表）

You are given an array a consisting of positive integers and q queries to this array. There are two types of queries:

• 1 l r x — for each index i such that l ≤ i ≤ r set ai = x.
• 2 l r — find the minimum among such ai that l ≤ i ≤ r.

We decided that this problem is too easy. So the array a is given in a compressed form: there is an array b consisting of n elements and a number k in the input, and before all queries a is equal to the concatenation of k arrays b (so the size of a is n·k).

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 104).

The second line contains n integers — elements of the array b (1 ≤ bi ≤ 109).

The third line contains one integer q (1 ≤ q ≤ 105).

Then q lines follow, each representing a query. Each query is given either as 1 l r x — set all elements in the segment from l till r(including borders) to x (1 ≤ l ≤ r ≤ n·k, 1 ≤ x ≤ 109) or as 2 l r — find the minimum among all elements in the segment from l till r(1 ≤ l ≤ r ≤ n·k).

Output

For each query of type 2 print the answer to this query — the minimum on the corresponding segment.

Examples
input

output

input

output

# SPOJ BGSHOOT – Shoot and kill（差分+ST表）

The problem is about Mr.BG who is a great hunter. Today he has gone to a dense forest for hunting and killing animals.

Sadly, he has only one bullet in his gun. He wants to kill as many animals as possible with only one bullet.

He has already known the information of duration availability of all animals of the forest.

So, he is planning to shoot at a time so that he could kill maximum animal.

### Input

Input begins with an integer N denoting total numbers of animals.

Next N lines contains the duration of availability of animal denoting by X (Starting time) and Y (Ending time) .

Then, there will be Q, denoting the total numbers of queries to be answer.

Each query giving two integer L and R, L denoting the time hunter will come to forest and begins shooting

and R denoting last time upto which he will stay at forest for hunting.

### Output

For each query output an integer denoting maximum numbers of animals he could kill by shooting at a time during L and R (inclusive).

Constraints:

1<=N,Q<=100000

1<=X,Y,L,R<=1000000000

mdzz。。。。

# BZOJ 1067: [SCOI2007]降雨量（ST表）

## Description

我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，

## Input

输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小

## Output

对于每一个询问，输出true，false或者maybe。

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

false
true
false
maybe
false

## HINT

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9