Dãy đèn

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 ~→~ chuyển sang vàng.
  • Nếu đang vàng ~→~ chuyển sang đỏ.
  • Nếu đang đỏ ~→~ 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 ~→~ chuyển sang đỏ.
  • Nếu đang đỏ ~→~ chuyển sang vàng.
  • Nếu đang vàng ~→~ 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.

Dữ liệu:

• 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 ≥ X + Y~ trong tất cả các yêu cầu.

Kết quả:

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.

Ví dụ

Input

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

Output

3
2
-1

Giải thích:

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:

Ràng buộc: