Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về yêu cầu đề và giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 2, có không quá ~500~ cứ điểm loại ~3~.

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không. Nếu có, hãy cho biết số quái vật ít nhất mà nhân vật của Quang phải chiến đấu là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.
• Với subtask 2, có không quá ~500~ cứ điểm loại ~3~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra số quái vật nhỏ nhất mà nhân vật của Quang phải chiến đấu.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 3
2 2 3 1 3
1 5 1 1
3 5 1 1
4 5 1 1

Dữ liệu ra

0
-1
1

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ máu ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.
• Trong kịch bàn thứ hai, cho dù Quang chọn chiến đấu hay chạy trốn thì máu hoặc thể lực của nhân vật đều về ~0~ và Quang thua trò chơi.
• Trong kịch bản cuối cùng, Quang nhận ~1~ điểm thể lực ở cứ điểm ~4~ và chiến đấu với quái vật ở cứ điểm ~5~. Do đó nhân vật của Quang phải đối đầu với ~1~ quái vật.