Cho dãy số nguyên dương a có n phần tử. Đồng chí hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không vượt quá s.

Dữ liệu vào:

• Dòng đầu tiên gồm 2 số nguyên dương, s (1<= n <= ~10^6~; 1 <= s <= ~10^{18}~)
• Dòng thứ hai gồm n số nguyên dương ~a_1, a_2, …, a_n~ (0 <= ~a_i~ <=~10^9~)

Dữ liệu ra:

In ra độ dài dãy con tìm được.

Ví dụ

Input

7 20
2 6 5 3 6 8 9

Output

4

Dãy số nguyên được xác định theo quy luật như sau:

~x_{0}~ = 1

~x_i~+1 = (a.~x_i~ + ~x_i~ div b) mod c

Đồng chí hãy tìm n nhỏ nhất sao cho tồn tại m < n và ~x_m~ = ~x_n~. Với n không quá 2.~10^7~

Giới hạn: 1 <= a <= ~10^4~ và 1 <= b, c <=~10^{14}~

Dữ liệu vào:

trong một dòng duy nhất chứa 3 số nguyên 1, b, c cách nhau bởi đấu cách.

Dữ liệu ra:

In ra giá trị n tìm được

Input

8 2 31

Output

9

Tom và những người bạn của mình đã quyết định đến đêm Halloween đi thu thập quà từ các gia đình trong làng như thường lệ. Vì ngôi làng quá lớn để nhóm các bạn trẻ có thể thu thập quà từ tất cả các gia đình theo trình tự, Tom và những người bạn quyết định chia nhau ra để mỗi người đến một gia đình khác nhau, thu thập quà (hoặc gây náo loạn nếu gia đình không phát quà) và sau đó quay trở lại điểm hẹn đã sắp xếp trước.

Có n gia đình trong làng, vị trí của các gia đình có thể được xác định bằng tọa độ Descartes trên mặt phẳng Euclid. Nhóm của Tom cũng gồm n thành viên. Họ đã quyết định phân phát quà sau khi mọi người trở về với chiến lợi phẩm của mình. Các gia đình có thể ở rất xa, nhưng Tom muốn ăn kẹo càng sớm càng tốt.

Nhóm của Tom ấn định địa điểm gặp nhau tại bờ dòng sông chạy qua làng (nằm trên trục tọa độ có y=0). Lưu ý, các hộ gia đình có thể năm ở cả hai bên bờ sông hoặc trên sông. Tốc độ di chuyển của mỗi thành viên trong nhóm là 1m/s theo bất kỳ hướng nào.

Đúng nửa đêm, mỗi thành viên trong nhóm sẽ gõ cửa gia đình mà mình đã chọn, lấy quà ngay lập tức và đi bộ trở lại theo tuyến đường ngắn nhất đến điểm gặp mặt. Đồng chí hãy cho biết Tom sẽ tới địa điểm đã hẹn vào thời điểm nào để anh ấy có thể bắt đầu ăn kẹo.

Đầu vào

• Dòng đầu tiên chứa 1 số nguyên dương n, biểu thị số gia đình (1 <= n <= 50000).
• N dòng tiếp theo mô tả vị trí của các gia đinh; mỗi dòng chứa hai số thực x, y (-200000 <= x, y <= 200000), tọa độ của một gia đình tính bằng mét. Tất cả các gia đình đều ở các vị trí khác nhau.

Đầu ra

In hai số trên một dòng cách nhau bởi một khoảng trắng: tọa độ x, y của điểm gặp nhau.

Ví dụ:

Input:

2 
1.5 1.5
3 0

Output

1.500000000 1.500000000

Input:

5 
4 7 
-4 0 
7 -6 
-2 4 
8 -5

Output:

3.136363636 7.13636366

Trong điện toán, khử trùng lặp dữ liệu là một kỹ thuật loại bỏ các bản sao trùng lặp của dữ liệu lặp lại. Việc triển khai thành công kỹ thuật này có thể cải thiện việc sử dụng lưu trữ, từ đó có thể giảm chi phí vốn bằng cách giảm tổng lượng phương tiện lưu trữ cần thiết để đáp ứng nhu cầu về dung lượng lưu trữ.

Trong dữ liệu nén có số nguyên N. Thì số nguyên N được lặp lại N lần đó là dữ liệu gốc. Ví dụ N=3 thì dữ liệu gốc là 333. Với N=8 thì dữ liệu gốc là 88888888

Hãy tìm số tự nhiên gốc của ~V_N~ đem chia module cho 998244353

Dữ liệu vào:

Từ dữ liệu chuẩn là số nguyên N (1 ≤ N ≤ ~10^{18}~)

Dữ liệu ra

Là số nguyên tìm được chia module cho 998244353

Ví dụ

input

5

ouput

55555

input

9

ouput

1755646