Gặp nhau cuối năm

Đã đến Tết Dương lịch, gần Tết Âm lịch nhưng Tade vẫn chưa có một kế hoạch đón Tết nào hết. Anh thậm chí còn chưa kịp mua đồ trang trí trong nhà!

Để Tết năm nay được có không khí... Tết, Tade quyết định sẽ bắt đầu bằng việc mua một cây đào trước. Thật may cho anh là những năm trước đây, gia đình anh có lưu một note ghi chép địa chỉ của một chỗ bán đào cực xịn. Nhưng cũng không may cho anh là tờ note tới giờ cũng đã 15 năm rồi nên nội dung còn khó đọc hơn chữ viết bác sĩ ¯\_(ツ)_/¯.

Các bạn hãy giúp Tade tìm lại địa chỉ của chỗ bán nhé! Biết nội dung trong tờ note là một xâu gồm các kí tự a tới z và các chữ số 0 tới 9, và địa chỉ nhà sẽ là số nguyên dương cấu thành từ chữ số đầu tiên của xâu ghép với chữ số cuối cùng của xâu. Lưu ý: nội dung của tờ note luôn đảm bảo có ít nhất 2 chữ số.

Input

• Một dòng duy nhất chứa xâu kí tự \(S\) \((1 \le |S| \le 10^5)\).

Output

• Một số nguyên dương duy nhất là địa chỉ của nơi bán đào uy tín đó (không có số \(0\) vô nghĩa ở đầu).

Sample

chuc3mungn4mm01202S

32

05/03/2025

5

Shop bán cây đào ấy hoạt động một cách rất thú vị: muốn mua cây thì phải gửi điện tín qua shop 2 ngày trước khi tới mua. Rõ ràng, năm 2025 thì còn ai dùng máy điện báo để gửi tin nữa, kể cả Tade. Kết cục là Tade phải đi mò cả ngày khắp hàng xóm mới kiếm được một cái máy cũ rích còn hoạt động, đã thế còn đôi khi bị lỗi nữa. Khi gửi một thông tin qua máy điện báo, nó sẽ tốn một khoảng thời gian nhất định mới được gửi qua, hoặc trong vài trường hợp hiếm, gửi trước khi cả Tade định bấm gửi (nói tóm lại là du hành thời gian). Để chỉnh lại delay của máy cho tuân theo các định luật vật lí, Tade sẽ so sánh thời gian gửi tín hiệu của nó với một bộ phận nhận tín hiệu khác anh có trong nhà để sửa lại, nhưng trước đó anh sẽ cần phải biết tổng thời gian lệch giữa các tín hiệu anh gửi và các tín hiệu anh nhận.

Cụ thể, Tade sẽ gửi \(n\) tín hiệu, cho thời gian gửi các tín hiệu của máy điện báo là \(a_1, a_2, a_3, \ldots, a_n\) và thời gian nhận của máy nhận tín hiệu là \(b_1, b_2, b_3, \ldots, b_n\). Tổng độ lệch tín hiệu của máy sẽ là tổng các \(|a_i - b_i|\) với \(1 \le i \le n\) sau khi sắp xếp lại a và b tăng dần.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \le n \le 10^5)\) - số lần phát tín hiệu.
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(a_i, b_i\) \((1 \le a_i, b_i \le 10^9)\).

Output

• Một số nguyên dương duy nhất là tổng độ lệch tín hiệu.

Sample

4
1 5
2 2
4 6
3 5

8

Gửi điện tín xong, Tade quyết định dành ngày hôm nay đi mua đá bỏ chậu chuẩn bị cho đào sắp về. Tại cửa hàng "Tiệm đá của thầy Bạch", chủ tiệm, thầy Bạch, vừa giới thiệu với Tade một loạt các loại đá mới với đủ các loại màu sắc, kích cỡ và hình dạng. Tuy vậy thầy Bạch chỉ luôn quan tâm tới màu sắc của các hòn đá của mình. Thầy Bạch có \(n\) màu đá khác nhau. Để sắp xếp và phân loại, mỗi màu của hòn đá được thầy Bạch đánh dấu với một giá trị \(i\) và có \(a_i\) viên đá của màu đó.

Tade rất ưng các mẫu đá của thầy Bạch và muốn chọn hết các màu, nhưng anh lại mắc hội chứng OCD, anh chỉ muốn mỗi màu chỉ có duy nhất một viên đá. Anh muốn biết có bao nhiêu cách khác nhau để chọn các viên đá. Khi đang chuẩn bị tính toán số lượng cách thì tiệm đào đã phản hồi lại điện tín của anh. Không còn cách nào khác, Tade sẽ để lại bài toán này cho các bạn.

Lưu ý: mỗi viên đá đều là riêng biệt.

Input

• Dòng đầu tiên chứa \(n\): số lượng màu sắc của các hòn đá \((1 \le n \leq 10^5)\).
• Dòng tiếp theo gồm \(n\) số nguyên không âm \(a_i\): số lượng viên đá của từng màu \(i\) \((0 \le a_i \leq 10^9)\).

Output

• Một số nguyên dương duy nhất là số cách chọn đá bỏ chậu. Vì số cách có thể rất lớn nên in ra kết quả sau khi chia dư \(10^9+7\).

Sample

2
1 2

2

3
3 0 4

0

Sau một ngày làm việc năng suất (Tade quyết định không mua viên đá nào vì chậu cây đã cho sẵn đá rồi), Tade cuối cùng cũng tìm đến tiệm hoa để sắm một chậu đào về trang trí Tết. Rõ ràng là việc phải dành nguyên 4 ngày để đi mua một chậu đào là quá lề mề nên Tade quyết định đẩy nhanh tiến độ, thay vì tới soi móc từng chậu đào để quyết định có mua hay không thì Tade sẽ lướt hết một lượt vài cây đào liên tiếp cho nhanh. Hơn nữa, vì quá lười nên Tade sẽ mua \(k\) cây đào luôn để cho \(k - 1\) năm sau còn có đào để trang trí (shop xịn tới mức bán đào bất tử).

Cho một dãy \(n\) cây hoa đào xếp liên tiếp trong shop và \(k\) là số đào Tade quyết định sẽ mua, hãy xác định độ dài \(d\) nhỏ nhất sao cho mọi đoạn con liên tiếp độ dài \(d\) của dãy cây luôn có ít nhất \(k\) chậu đào trên đoạn đó.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((1 \le k \le n \le 10^5)\) - số chậu đào và số đào Tade muốn mua.
• Dòng tiếp theo chứa một xâu kí tự độ dài \(S\) bao gồm hai kí tự:
  • . nếu vị trí hiện tại không có đào (họ mua rồi)
  • # nếu vị trí hiện tại có đào (cây ế)

Output

• Một dòng duy nhất chứa số nguyên dương \(d\) là độ dài nhỏ nhất cần tìm, nếu không có số \(d\) nào thỏa mãn thì in ra \(-1\).

Sample

5 1
..#.#

3

6 4
.##..#

-1