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 $\to$ chuyển sang vàng.
  • Nếu đang vàng $\to$ chuyển sang đỏ.
  • Nếu đang đỏ $\to$ 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 $\to$ chuyển sang đỏ.
  • Nếu đang đỏ $\to$ chuyển sang vàng.
  • Nếu đang vàng $\to$ 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 vào

• 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.

Dữ liệu ra

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.

Ràng buộc

• $X,Y\ge 0$; $0<X+Y\le 5$; $X+Y\le N\le 666$; $1\le Q\le {10}^5$.
• Trạng thái mỗi bóng đèn là $0$, $1$ hoặc $2$.
• Mỗi yêu cầu: $1\le L\le R\le N$ và $R-L+1\ge X+Y$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $X=Y=1$; $N\le 10$; $Q=1$.
• Subtask 2 ($20\%$ số điểm): $X=Y=1$; $Q=1$.
• Subtask 3 ($34\%$ số điểm): $Q\le 5$.
• Subtask 4 ($16\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ