Dãy con ngắn nhất

Dãy số $a_1,a_2,\dots ,a_n$ được lập theo qui tắc sau: $a_1=x$, $a_2=y$, $a_k=(a_{k-1}+a_{k-2})modM$ với mọi $k=3,4,\dots ,n$. Ở đây phép toán $pmodq$ là phép lấy phần dư khi chia $p$ cho $q$ (phép % trong ngôn ngữ C++ và Python).

Cho số nguyên dương $S$.

Yêu cầu: Hãy tìm dãy con $a_i,a_{i+1},\dots ,a_j$ có số lượng phần tử nhỏ nhất sao cho: $a_i+a_{i+1}+\dots +a_j\ge S$.

Dữ liệu vào

Một dòng duy nhất chứa $5$ số nguyên $n,x,y,M,S$ cách nhau bằng khoảng trống.

Dữ liệu ra

Một số nguyên duy nhất là số lượng phần tử của dãy con tìm được. Nếu không tồn tại dãy con thoả mãn thì in $-1$.

Ràng buộc

• $2\le n\le 2\times {10}^5$.
• $1<M\le {10}^4$.
• $0\le x,y<M$.
• $1\le S\le {10}^{15}$.

Subtasks

• Subtask 1 ($40\%$ số điểm): $n\le 300$.
• Subtask 2 ($30\%$ số điểm): $n\le 5000$.
• Subtask 3 ($30\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ