Bir dizi ve bir desen kümesi verildiğinde, her bir desen için bu desenin dizide kaç farklı pozisyonda geçtiğini bulunuz.
İlk satırda n~(1 \le n \le 10^5) uzunluğunda bir dizi verilir.
İkinci satırda desen sayısını belirten bir tam sayı k~(1 \le k \le 5 \cdot 10^5) verilir. Sonraki satırın her birinde bir desen bulunur. Tüm desenlerin toplam uzunluğu 5 \cdot 10^5'i geçmez.
Dizi ve desenler küçük Latin harflerinden '' - '' oluşur.
Her bir desen için, bu desenin dizi içinde kaç kez geçtiğini ayrı bir satırda yazdırınız.
Örnek 1