Clubbing
本题没有可用的提交语言。
Description
Students of Tomorrow Programming School engage in different school programming clubs. Each student is a member of some number of clubs. The clubs are supervised by the Principal Club Coach (PCC). His main occupation is to talk to club members to help them organize their activities. PCC has a fixed schedule in the form of a list of students he is going to talk to in the nearest future. He always talks to only one student at a time, he may talk to a student repeatedly at various times. Each talk takes short time interval, which is always the same. There is negligible time between subsequent talks.
Currently, the school director also needs to talk to some students in the presence of PCC, because he needs to start another state supported programming project. He is going to visit PCC's cabinet and spend some uninterrupted time there. In that time, he wants to talk to all members of at least one club. Thus, PCC defined a so-called director interval in his schedule. It is an uninterrupted sequence of his talks to students, in which all members of at least one club appear at least once.
Before he suggests an acceptable director interval, PCC at least wants to know the number of such intervals in his schedule.
The first input line contains one integer $N$ ($1 \leq N \leq 10^5$), the number of student clubs. Next $N$ lines contain the list of club members, each line specifies one club. One club is specified by a string without spaces, in which each member is represented by a single character. All characters in the string are different. The last input line contains the schedule of PCC, in the form of nonempty string with at most $10^5$ characters, each character represents one student. In all strings, each character is one of the first $17$ lowercase letters in the alphabet("a" - "q").
Output one integer, the number of director intervals in PCC's schedule.
Input
The first input line contains one integer $N$ ($1 \leq N \leq 10^5$), the number of student clubs. Next $N$ lines contain the list of club members, each line specifies one club. One club is specified by a string without spaces, in which each member is represented by a single character. All characters in the string are different. The last input line contains the schedule of PCC, in the form of nonempty string with at most $10^5$ characters, each character represents one student. In all strings, each character is one of the first $17$ lowercase letters in the alphabet("a" - "q").
Output
Output one integer, the number of director intervals in PCC's schedule.
2
pid
lid
lidp
2
baf
lek
affleck
3
4