Truy vấn nhỏ nhất trên dãy tuần hoàn

Cho dãy $b$ gồm $n$ số nguyên dương và một số nguyên $k$. Dãy $a$ được tạo ra bằng cách nối liên tiếp $k$ bản sao của dãy $b$, do đó $a$ có đúng $n·k$ phần tử:

$$a=\underset{k\text{ lần}}{\underbrace{b_1,b_2,\dots ,b_n,b_1,b_2,\dots ,b_n,\dots ,b_1,b_2,\dots ,b_n}}$$

Nói cách khác, $a_i=b_{((i-1)modn)+1}$ với mọi $1\le i\le n·k$.

Bạn cần xử lý $q$ truy vấn trên dãy $a$, mỗi truy vấn thuộc một trong hai loại:

• 1 l r x — gán $a_i=x$ với mọi chỉ số $i$ thỏa mãn $l\le i\le r$.
• 2 l r — tìm giá trị nhỏ nhất trong các $a_i$ với $l\le i\le r$.

Các truy vấn phải được xử lý theo đúng thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$.
• Dòng thứ ba chứa một số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng 1 l r x hoặc 2 l r như trên.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra trên một dòng giá trị nhỏ nhất của đoạn tương ứng.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le k\le {10}^4$
• $1\le b_i\le {10}^9$
• $1\le q\le {10}^5$
• $1\le l\le r\le n·k$
• $1\le x\le {10}^9$

Lưu ý rằng $n·k$ có thể lên tới ${10}^9$, nên không thể dựng tường minh toàn bộ dãy $a$.

Ví dụ