Quà Noel

Ông già Noel đã chuẩn bị $N$ loại quà, loại quà thứ $i$ ($1\le i\le N$) có $S_i$ món và khối lượng mỗi món là $W_i$ gram. Ông dự định đóng gói các túi quà để phát cho trẻ em ở VOI sao cho mỗi túi có đúng $K$ món và không có hai món nào cùng một loại quà. Tuy nhiên, xe tuần lộc của ông chỉ có thể mang được không quá $M$ gram quà.

Để chuẩn bị chu đáo trước khi lên đường, ông già Noel đưa ra một loạt $Q$ câu hỏi cho trợ lý của ông tính toán, mỗi câu hỏi thuộc một trong hai loại sau:

• Loại 1: Cho biết $3$ giá trị $M,K,T$, hãy kiểm tra xem có thể tạo ra được $T$ túi quà mà tổng khối lượng các món quà trong cả $T$ túi đó không vượt quá $M$ gram hay không?
• Loại 2: Cho biết $2$ giá trị $M,K$, hỏi có thể tạo ra được nhiều nhất bao nhiêu túi quà mà tổng khối lượng các món quà trong tất cả các túi đó không vượt quá $M$ gram?

Yêu cầu: Hãy giúp trợ lý trả lời từng câu hỏi của ông già Noel.

Dữ liệu vào

• Dòng đầu chứa $2$ số nguyên $N,Q$ ($1\le N,Q\le {10}^5$).
• Dòng thứ hai chứa $N$ số nguyên dương $W_1,W_2,\dots ,W_N$ có giá trị không quá ${10}^5$.
• Dòng thứ ba chứa $N$ số nguyên dương $S_1,S_2,\dots ,S_N$ có giá trị không quá ${10}^5$.
• Mỗi dòng trong số $Q$ dòng tiếp theo thể hiện một câu hỏi thuộc một trong hai loại:
  • Loại 1: $1$ $M$ $K$ $T$ ($1\le M,K,T\le {10}^9$).
  • Loại 2: $2$ $M$ $K$ ($1\le M,K\le {10}^9$).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng thể hiện câu trả lời cho một câu hỏi tương ứng:

• Loại 1: In ra $1$ nếu có thể tạo được $T$ túi quà, trái lại in ra $0$.
• Loại 2: In ra một số nguyên là số lượng túi quà nhiều nhất tạo được.

Ràng buộc

• $1\le N,Q\le {10}^5$.
• $1\le W_i,S_i\le {10}^5$.
• $1\le M,K,T\le {10}^9$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $S_i=1$.
• Subtask 2 ($20\%$ số điểm): $N,Q\le 1000$ và chỉ có câu hỏi loại 1.
• Subtask 3 ($15\%$ số điểm): $N,Q\le 1000$.
• Subtask 4 ($20\%$ số điểm): Chỉ có câu hỏi loại 1.
• Subtask 5 ($20\%$ số điểm): Không có ràng buộc nào thêm.

Ví dụ