Ông già Noel đã chuẩn bị ~N~ loại quà, loại quà thứ ~i~ (~1 ≤ i ≤ 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.

Input

Vào từ file văn bản GIFT.INP:

• Dòng đầu chứa ~2~ số nguyên ~N, Q~ (~1 ≤ N, Q ≤ 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên dương ~W_1, W_2, ..., 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, ..., 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 ≤ M, K, T ≤ 10^9~).

  • Loại 2: ~2~ ~M~ ~K~ (~1 ≤ M, K ≤ 10^9~).

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

Output

Ghi ra file văn bản GIFT.OUT:

• 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: Ghi ra ~1~ nếu có thể tạo được ~T~ túi quà, trái lại ghi ra ~0~.

• Loại 2: Ghi ra một số nguyên là số lượng túi quà nhiều nhất tạo được.

Scoring

Sample Input 1

5 3
8 3 4 10 8
5 8 2 9 10
1 19 3 2
2 19 3
2 9 1

Sample Output 1

0
1
3

Notes

• Với câu hỏi 1: Không có cách nào chọn được hai túi, mỗi túi có ~3~ món mà tổng khối lượng không quá ~19~ gram.

• Với câu hỏi 2: Tạo ra được nhiều nhất một túi quà. Một phương án là túi quà gồm một món quà loại ~2~, một món quà loại ~3~ và một món quà loại ~4~. Tổng khối lượng là ~17~ gram.

• Với câu hỏi 3: Tạo ra được nhiều nhất ba túi quà. Mỗi túi gồm đúng một món quà loại ~2~.