F. Far-reaching Citations
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Managing citations in academic writing can be challenging. As you are near the completion of a paper draft, it's common to realize that you've lost track of the sources for your ideas. Properly citing relevant papers is essential to highlight their contributions and establish the novelty of your work. Failure to do so not only makes it difficult for reviewers to assess your paper but also raises concerns about plagiarism. Inadequate citations can ultimately diminish your paper's chances of acceptance.

Rebecca needs help assessing her citation needs for her upcoming publication. The world of academic papers is complex, with some being entirely original while others build upon existing works. There are $$$N$$$ published papers, labeled as $$$s_i$$$ for $$$1 \leq i \leq N$$$. Certain papers directly extend earlier ones by adding new content, written as $$$s_i = s_j\ ||\ u_i$$$, where $$$u_i$$$ is a non-empty string appended to a previous work $$$s_j$$$. If a paper is created independently, it is represented as $$$s_i = u_i$$$.

Rebecca's own paper, represented as string $$$t$$$, is in question. For each distinct pair of indices $$$i$$$ and $$$j$$$ $$$(1\leq i\le j\leq |t|)$$$, if the substring $$$t[i..j] = t_it_{i+1}..t_j$$$ occurs $$$x$$$ times within paper $$$s_k$$$, she must add $$$x$$$ citations to paper $$$k$$$. For instance, if $$$t=$$$abc and $$$s_1=$$$abab, the substring $$$t[1,2]=$$$ab alone would contribute $$$2$$$ citations to paper $$$s_1$$$. The total count of citations required is the sum across all preceding papers $$$s_k\ (1\leq k\leq N)$$$. The task is to determine this total.

Input

The input begins with an integer $$$N\ (1\leq N\leq 10^5)$$$, denoting the number of published papers.

Subsequently, there are $$$N$$$ lines, the $$$i$$$-th line consisting an integer $$$j\ (0\leq j \lt i)$$$ and a string $$$u_i$$$, separated by a space. A positive $$$j$$$ means that paper $$$s_i$$$ directly extends an existing work $$$s_j$$$ (so $$$s_i = s_j\ ||\ u_i$$$), while $$$j=0$$$ indicates that $$$s_i$$$ is an independent paper ($$$s_i = u_i$$$).

The final line holds the string $$$t\ (1\leq |t|\leq 10^5)$$$, representing Rebecca's own paper.

All input strings are composed of lowercase characters. The combined length of all $$$u_i$$$ strings is guaranteed not to exceed $$$10^5$$$.

Output

The output is a single integer representing the total count of citations required for Rebecca's own paper.

Hint: The range of possible outputs sits within the range of unsigned long long.

Examples
Input
3
0 b
1 c
0 dc
bcdc
Output
9
Input
5
0 ab
1 bc
1 bcd
1 cde
0 abc
abcde
Output
39
Note

The first sample has $$$3$$$ papers, $$$s_1=$$$b, $$$s_2=$$$bc, $$$s_3=$$$dc, among which $$$5$$$ distinct substrings of $$$t=$$$bcdc appeared:

  • $$$t[1,1]=$$$b, which appeared $$$1+1+0=2$$$ times in the papers.
  • $$$t[2,2]=t[4,4]=$$$c, each appeared $$$0+1+1=2$$$ times in the papers, so they contribute $$$2\times 2=4$$$ citations in total.
  • $$$t[3,3]=$$$d, which appeared $$$0+0+1=1$$$ time in the papers.
  • $$$t[1,2]=$$$bc, which appeared $$$0+1+0=1$$$ time in the papers.
  • $$$t[3,4]=$$$dc, which appeared $$$0+0+1=1$$$ time in the papers.

In total, the number of citations required is $$$2+4+1+1+1=9$$$.