Cho hai dãy số nguyên \(a, b\) có cùng độ dài \(n\) và một số nguyên \(S\). Có \(Q\) truy vấn thuộc một trong hai dạng sau:

• \(1\) \(i\) \(x\) \(y\): Gán \(a_{i} = x, b_{i} = y\).
• \(2\) \(H\): Cần tìm \(1 \leq L \leq H\) sao cho \(a_{L} + a_{L + 1} + \ldots + a_{H} \geq S\) và \(b_{L} + b_{L + 1} + \ldots + b_{H}\) đạt giá trị nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, S\) \((1 \leq n \leq 10^{5}, −10^{18} \leq S \leq 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((−10^{9} \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((−10^{9} \leq b_{i} \leq 10^{9})\).
• Dòng thứ tư chứa số nguyên dương \(Q\) \((1 \leq Q \leq 10^{5})\).
• \(Q\) dòng tiếp theo, mỗi dòng ghi một truy vấn: \(1\) \(i\) \(x\) \(y\) \((1 \leq i \leq n, −10^{9} \leq x, y \leq 10^{9})\) hoặc \(2\) \(H\) \((1 \leq H \leq n)\).

Output

• Với mỗi truy vấn, in ra trên một dòng là giá trị nhỏ nhất có thể của \(b_{L} + b_{L + 1} + \ldots + b_{H}\) hoặc \(-1\) nếu không tồn tại \(L\) thoả mãn.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(a_{i} = 1\) tại mọi thời điểm.
• Subtask \(2\) (\(25\%\) số điểm): \(b_{i} = 1\) tại mọi thời điểm.
• Subtask \(3\) (\(25\%\) số điểm): Các truy vấn loại \(2\) nằm liên tiếp nhau.
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc nào thêm.

Example

6 5
2 1 -1 3 -2 4
1 1 1 1 1 1
3
2 4
1 3 1 1
2 4

4
3