Ở trấn ByteTown miền Viễn Tây có một trang trại cho thuê ngựa rất nổi tiếng. Các cao bồi và dân buôn vùng này luôn tìm đến đây để thuê những chú ngựa khỏe mạnh cho những chuyến đi xa của mình. Có \(N\) cửa hàng cho thuê, được đánh số theo thứ tự từ \(1\) đến \(N\) từ cổng vào trang trại (càng xa cổng thì số hiệu càng lớn). Cửa hàng thứ \(i\) cho một khách hàng thuê tối đa là \(h_i\) chú ngựa trong một lần thuê, nhưng giới hạn này có thể được thay đổi tùy theo thời điểm. Vì diện tích trang trại ngựa này là cực kỳ rộng lớn, nên các khách hàng muốn thuê từ những cửa hàng gần nhất sao cho tổng số lượng thuê được đạt với yêu cầu đặt ra. Hãy lập trình tính toán giúp các vị khách hàng khó tính này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,\ Q\) - lần lượt là số cửa hàng cho thuê ngựa và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên dương \(h_1,\ h_2,\ldots,\ h_N\) là giới hạn cho thuê ngựa của mỗi cửa hàng lúc ban đầu;
• \(Q\) dòng tiếp theo thể hiện các truy vấn. Có hai loại truy vấn được biểu diễn dưới dạng:
  • "\(1\ l\ r\ x\)" - giới hạn cho thuê ngựa của mỗi cửa hàng trong đoạn từ \(l\) đến \(r\) tăng một lượng \(x\) dương;
  • "\(2\ v\)" - in ra số \(k\) là số nhỏ nhất sao cho khi khách hàng thuê ngựa từ cửa hàng \(1\) đến cửa hàng thứ \(k\) thì tổng số lượng ngựa có thể thuê lớn hơn hoặc bằng \(v\). Nếu không tồn tại, in \(-1\).

Output

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

Ví dụ

Sample input

5 3
4 2 3 7 2 
2 9
1 1 3 2
2 10

Sample output

3
2

Ràng buộc

• \(1\leq l, r\leq N\leq10^5\);
• \(1\leq h_i,\ x\leq10^9\);
• \(1\leq v\leq10^{15}\).
• Có \(50\%\) số test tương ứng với \(50\%\) số điểm của bài toán có \(1\leq Q\leq10^5\);
• Có \(50\%\) số test còn lại tương ứng với \(50\%\) số điểm còn lại có \(1\leq Q\leq10^6\);