Giáng sinh năm nay, khu phố VOI được trang trí bởi một dàn ~N~ bóng đèn, các bóng đèn được đánh số từ ~1~ đến ~N~. Ban đầu, mỗi bóng đèn ở một trong 3 trạng thái: tắt, vàng hoặc đỏ. Mỗi bóng đèn được điều khiển bởi một công tắc vòng tròn hoạt động như sau:

• Khi xoay theo chiều kim đồng hồ một nấc, trạng thái bóng đèn thay đổi:

  • Nếu đang tắt ~\rightarrow~ chuyển sang vàng.

  • Nếu đang vàng ~\rightarrow~ chuyển sang đỏ.

  • Nếu đang đỏ ~\rightarrow~ chuyển sang tắt.

• Khi xoay ngược chiều kim đồng hồ một nấc, trạng thái bóng đèn thay đổi:

  • Nếu đang tắt ~\rightarrow~ chuyển sang đỏ.

  • Nếu đang đỏ ~\rightarrow~ chuyển sang vàng.

  • Nếu đang vàng ~\rightarrow~ chuyển sang tắt.

Ban quản trị VOI nhận được ~Q~ yêu cầu khảo sát. Mỗi yêu cầu gồm hai giá trị ~L~ và ~R~ với ~1 \le L \le R \le N~. Cụ thể, mỗi yêu cầu cần tìm một dãy các thao tác để đưa tất cả các bóng đèn từ ~L~ đến ~R~ về trạng thái tắt. Mỗi thao tác được thực hiện như sau:

Chọn ~X + Y~ bóng đèn phân biệt trong đoạn từ ~L~ đến ~R~, trong đó:

• ~X~ bóng đèn để xoay công tắc theo chiều kim đồng hồ một nấc.

• ~Y~ bóng đèn còn lại để xoay công tắc ngược chiều kim đồng hồ một nấc.

Lưu ý: Các yêu cầu khảo sát là độc lập, nghĩa là mỗi yêu cầu đều được xử lý trên trạng thái ban đầu của dãy đèn. Giá trị ~X~ và ~Y~ cố định cho tất cả ~Q~ yêu cầu. Các công tắc vòng tròn có thể xoay không giới hạn theo cả hai chiều.

Yêu cầu: Với mỗi yêu cầu khảo sát, hãy tìm số thao tác ít nhất để đưa toàn bộ các bóng đèn trong đoạn từ ~L~ đến ~R~ về trạng thái tắt.

Input

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

• Dòng đầu tiên chứa 4 số nguyên không âm ~N, Q, X, Y~ (~0 < X + Y \le 5~, ~X + Y \le N \le 666~, ~1 \le Q \le 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ có giá trị ~0~, ~1~ hoặc ~2~ tương ứng với trạng thái ban đầu của bóng đèn thứ ~i~ là tắt, vàng hoặc đỏ (~1 \le i \le N~).

• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~L~ và ~R~ mô tả một yêu cầu. Dữ liệu bảo đảm ~R - L + 1 \ge X + Y~ trong tất cả các yêu cầu.

Output

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

• Gồm ~Q~ dòng, mỗi dòng một số nguyên là số lượng thao tác ít nhất tìm được cho yêu cầu khảo sát tương ứng hoặc ~-1~ nếu không tồn tại phương án.

Scoring

Sample Input 1

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

Sample Output 1

3
2
-1

Notes

Yêu cầu của khảo sát đầu tiên cần ít nhất 3 thao tác. Hình sau minh họa 1 dãy thao tác tối ưu:

Ô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~.

Alice là kỹ sư phát triển nền tảng mạng xã hội VOI giúp cho cộng đồng lập trình viên tương tác với nhau. Có ~N~ bài đăng được đánh số từ ~1~ đến ~N~ theo trình tự thời gian đăng bài. Alice phân loại các bài đăng theo chủ đề, bài đăng thứ ~i~ ~(1 \le i \le N)~ có chủ đề là ~A_i~.

Alice định nghĩa một đoạn ~[L, R]~ gồm các bài đăng liên tiếp từ chỉ số ~L~ đến chỉ số ~R~ ~(1 \le L \le R \le N)~ là toàn vẹn nếu với mỗi chủ đề ~t~, hoặc không có bài nào có chủ đề ~t~ nằm trong đoạn ~[L, R]~ hoặc tất cả các bài có chủ đề ~t~ đều nằm trong đoạn này.

Yêu cầu: Vào dịp Noel, Alice công bố dữ liệu chủ đề của ~N~ bài đăng và mở cuộc thi trên VOI cho các lập trình viên tham gia. Alice lần lượt đưa ra ~Q~ truy vấn, mỗi truy vấn cho biết một cặp số nguyên ~U, V~ ~(1 \le U \le V \le N)~ và yêu cầu thí sinh đếm số đoạn ~[L, R]~ là toàn vẹn với ~U \le L \le R \le V~.

Cụ thể, với mỗi truy vấn, cần đếm xem có bao nhiêu cặp ~L, R~ thỏa mãn:

• ~U \le L \le R \le V~;

• Không tồn tại hai giá trị ~i, j~ nào sao cho:

  • ~(1 \le i < L)~ hoặc ~(R < i \le N)~;

  • ~L \le j \le R~;

  • ~A_i = A_j~.

Input

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

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_1, A_2, \ldots, A_N \le 10^9)~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~U~ và ~V~.

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 POST.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số là đáp án cho truy vấn tương ứng.

Scoring

Sample Input 1

7 2
1 2 2 3 1 6 3
1 7
2 6

Sample Output 1

3
2

Notes

• Truy vấn 1, có 3 đoạn toàn vẹn:

$$[1,7], [2,3], [6,6]$$

• Truy vấn 2, có 2 đoạn toàn vẹn:

$$[2,3], [6,6]$$