Tết Kỷ Hợi năm nay vì muốn chiến thắng trong trò chơi với Tủm, Tũn ta ra sức viết thật nhiều lời chúc để hòng nhận được nhiều xiền lì xì hơn. Một lời chúc được gọi là tốt đẹp khi nó chứa nhiều “lucky word”. Một từ được gọi là may mắn nếu có một phép hoán vị biến từ đó thành “lucky word”. Vì học văn khá dở nên Tũn không thể biết được lời chúc của mình có tốt đẹp hay không các bạn hãy giúp Tũn nhé! Cho lời chúc của Tũn hãy xác định xem độ may mắn của lời chúc đó và thông báo đến Tũn. (độ may mắn của lời chúc được đo bằng số lượng từ từ may mắn xuất hiên trong lời chúc)
INPUT:
- Dòng đầu chứa một số nguyên dương n là độ dài lời chúc của Tũn (n<=10^5)
- Dòng tiếp theo chứa lời chúc của Tũn chỉ gồm các chữ cái in thường trong bảng chữ cái tiếng Anh
- Dòng tiếp theo chứa một sô nguyên dương q là độ dài “lucky word” (q<=n)
- Dòng cuối cùng chứa “lucky word” chỉ gồm các chữ cái in thường trong bản chữ cái tiếng Anh
OUTPUT:
- Chỉ gồm một số nguyên duy nhất là độ may mắn của lời chúc