Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Периодическая задача RMQ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a, состоящий из натуральных чисел, и q запросов к нему. Запросы бывают двух видов:

  • 1 l r x — для всех таких индексов i, что l ≤ i ≤ r, присвоить ai = x.
  • 2 l r — найти минимум по всем таким ai, что l ≤ i ≤ r.

Мы решили, что эта задача слишком простая. Поэтому массив a задаётся в сжатом виде: во входном файле записаны массив b длины n и число k, а изначальный массив 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 типа выведите ответ на него — число, равное минимуму на соответствующем подотрезке в момент запроса.

Примеры
Входные данные
3 1
1 2 3
3
2 1 3
1 1 2 4
2 1 3
Выходные данные
1
3
Входные данные
3 2
1 2 3
5
2 4 4
1 4 4 5
2 4 4
1 1 6 1
2 6 6
Выходные данные
1
5
1