Trong hội xuân có chương trình thi đấu giữa đô vật vô địch tỉnh với các trai làng. Có \(n\) chàng trai muốn thử sức với nhà vô địch, đứng xếp hàng trước xới đấu. Với kinh nghiệm dày dạn của mình, nhà vô địch chỉ nhìn lướt qua là đánh giá được tiềm lực của mỗi người, cụ thể, người thứ \(i\) có tiềm lực \(s_i\), \(i = 1 - n\). Với tiềm lực \(T\) của mình, sau khi thi đấu với người thứ i, tiềm lực của nhà vô địch sẽ giảm xuống còn \(⎣T/si⎦\) (kết quả của phép chia nguyên). Nếu tiềm lực bị giảm xuống bằng \(0\) nhà vô địch sẽ thua và bị loại khỏi cuộc chơi, không thi đấu tiếp nữa. Các chàng trai không phải là những vận động viên chuyên nghiệp, vì vậy sự chờ đợi sốt ruột và căng thẳng đã làm cho tiềm lực các người từ vị trí \(L\) đến \(R\) bị giảm đi \(1\), cụ thể là \(s_i = max\{s_i-1, 1\}\), \(i = L ... R\). Nhà vô địch quan sát thấy sự suy giảm tiềm lực ở một số chàng trai và nhẩm tính với tiềm lực hiện tại \(x\) của mình, nếu chọn thi đấu với các chàng trai từ vị trí \(L\) đến vị trí \(R\) và lần lượt đấu từ trái sang phải với những người trong đoạn đó thì có bị thua hay không, nếu bị thua thì là ở dưới tay ai.

Dữ liệu

Vào từ thiết bị nhập chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\), trong đó \(q\) – số truy vấn cần xử lý \((1 ≤ n, q ≤ 5×10^5)\).
• Dòng thứ hai chứa n số nguyên \(s_1, s_2, . . ., s_n\) \((1 ≤ s_i ≤ 1000, i = 1 ... n)\), Mỗi dòng trong \(q\) dòng tiếp theo chứa thông tin ở một trong hai dạng:
  • \(1\:L\:R\) – tiềm lực hiện tại của người từ \(L\) đến \(R\) bị giảm đi \(1\) khi gặp truy vấn này.
  • \(2\:L\:R\:x\) – nhà vô địch có tiềm lực \(x\) \((1 ≤ x ≤ 10^9)\) và chọn thi đấu lần lượt với các người từ \(L\) đến \(R\).

Trong cả hai loại truy vấn: \(1 ≤ L ≤ R ≤ n\).

Kết quả

Đưa ra thiết bị xuất chuẩn, với mỗi truy vấn loại \(2\) đưa ra trên một dòng thông báo \(-1\) – nhà vô địch thắng hoặc một số nguyên – người hạ đo ván nhà vô địch.

Ví dụ

Dữ liệu:

6 4
1 2 3 2 3 1
2 1 6 61
2 1 3 2
1 1 3
2 1 3 2

Kết quả:

-1
3
-1

Subtask

\(30\%\) số test có \(n, q \le 5000\).

\(40\%\) số test có \(n, q \le 50000\).