An lưu trên máy tính một tệp nhật ký, là một chuỗi gồm N sự kiện được ghi lại. Mỗi sự kiện được thể hiện bởi một số nguyên mà chỉ có An mới biết được ý nghĩa của nó. Bảo mật độ K của tệp nhật ký là số cặp số nguyên trong chuỗi sự kiện có tổng bằng K.

Thật không may máy tính của An bị vi rút xâm nhập và tệp nhật ký đã bị nhiễm vi rút. Chuỗi sự kiện đã bị thay đổi bởi những chữ cái La tinh in thường và dấu cách được chèn vào giữa các sự kiện. Hệ điều hành của máy tính An nhận diện được vi rút và cảnh báo một mã lỗi là một số nguyên S (|S| ≤ 10⁹). An hiểu được, muốn khôi phục lại tệp nhật ký ban đầu cần phải xác định độ bảo mật độ S của tệp nhật ký đó.

Yêu cầu: Với tệp bị nhiễm vi rút nói trên, nhiệm vụ của bạn là giúp An xác định được độ bảo mật của tệp nhật ký để An có thể khôi phục lại dữ liệu của mình.

Dữ liệu vào:

+ Dòng đầu là một số nguyên dương N (N ≤ 10⁶).

+ Dòng thứ hai là xâu kí tự thể hiện tệp nhật ký bị nhiễm vi rút, gồm các chữ cái La tinh in thường và dấu cách được chèn vào giữa các sự kiện.

+ Dòng thứ ba gồm một số nguyên S là mã lỗi mà hệ điều hành thông báo.

Các số nguyên thể hiện cho các sự kiện có có giá trị tuyệt đối không quá 10⁹.

Kết quả: Ghi ra tệp văn bản NHATKY.OUT gồm một số nguyên là độ bảo mật độ S của tệp nhật ký.

Ví dụ:

Ràng buộc:

+ Subtask 1: Có 30% số test tương ứng với 30% số điểm có 100 < N ≤ 10⁴, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.

+ Subtask 2: Có 20% số test tương ứng với 20% số điểm có 10⁴ < N ≤ 10⁵, tệp nhật ký bị nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.

+ Subtask 3: Có 30% số test tương ứng với 30% số điểm có 2 ≤ N ≤ 100 và không có ràng buộc gì thêm.

+ Subtask 4: Có 20% số test tương ứng với 20% số điểm có 10⁵ < N ≤ 10⁶ và không có ràng buộc gì thêm.