Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Periodic RMQ Problem

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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*a*_{i}=*x*. - 2
*l**r*— find the minimum among such*a*_{i}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* ≤ 10^{5}, 1 ≤ *k* ≤ 10^{4}).

The second line contains *n* integers — elements of the array *b* (1 ≤ *b*_{i} ≤ 10^{9}).

The third line contains one integer *q* (1 ≤ *q* ≤ 10^{5}).

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* ≤ 10^{9}) 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

3 1

1 2 3

3

2 1 3

1 1 2 4

2 1 3

Output

1

3

Input

3 2

1 2 3

5

2 4 4

1 4 4 5

2 4 4

1 1 6 1

2 6 6

Output

1

5

1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2018 16:46:38 (f2).

Desktop version, switch to mobile version.

User lists

Name |
---|