Cho một mảng \(a\) gồm \(n\) phần tử, các phần tử có giá trị trong khoảng từ \(0\) tới \(10^9\). Bạn được yêu cầu xử lý \(Q\) truy vấn, với các truy vấn như sau:

1. \(1\ l\ r\ w\): Gán giá trị các phần tử từ vị trí \(l\) tới \(r\) thành \(w\).
2. \(2\ l\ r\): Tìm phần tử lớn nhất hiện tại trong đoạn từ \(l\) tới \(r\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n\) và \(Q\), lần lượt là kích thước của mảng và số lượng truy vấn.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((0 \leq a_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng:
• \(1\ l\ r\ w\) \((1 \leq l \leq r \leq n,\ 0 \leq w \leq 10^9)\): Gán giá trị các phần tử từ vị trí \(l\) tới \(r\) thành \(w\).
• \(2\ l\ r\) \((1 \leq l \leq r \leq n)\): Tìm phần tử lớn nhất hiện tại trong đoạn từ \(l\) tới \(r\).

Output

• In ra kết quả cho các truy vấn loại \(2\), mỗi truy vấn in trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(n, Q \leq 10^5\).

Ví dụ

5 8
1 2 3 4 5
2 1 3
2 2 5
1 1 2 2
2 1 3
2 2 5
1 4 5 1
2 1 3
2 2 5

3
5
3
5
3
3