הפרות מסתבכות שוב ושוב בנסיעות בטרקטור של Farmer John, ולכן החביא את המפתחות בכספת חדשה מהודרת במשרדו. ללא פחד, הן החליטו לנסות לפרוץ אותה.

לכספת מערכת קוד מסובכת. ההזנה בנויה כעץ מושרש עם $N$ צמתים ($1 \leq N \leq 20,000$), שכל אחד דורש ספרה מ־0 עד 9. הצמתים ממוספרים $0..N-1$.

הן יודעות רק שרצפים מסוימים באורך 5 אינם מופיעים במסלולים מסוימים כלפי מעלה בעץ.

למשל, נניח עץ כזה ששורשו A:

A <- B <- C <- D <- E
               ^
               |
               F

ייתכן שהן יודעות ש־01234 אינו מופיע החל ב־$F$, ו־91234 החל ב־$E$. זה פוסל 19 קודים, כל אלה מהצורה:

4 <- 3 <- 2 <- 1 <- *
               ^
               |
               0

או

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               *

בהתחשב בכך שהתצורה הבאה:

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               0

מופיע פעמיים, מתקבלים 19.

בהינתן $M$ רצפים באורך 5 ($1 \leq M \leq 50,000$) וצמתי ההתחלה שלהם, חשבו כמה קודים נפסלו, מודולו 1234567.

קלט

• שורה $1$: השלמים $N$ ו־$M$, מופרדים ברווח.
• שורות $2..N$: שורה $i+1$ מכילה את השלם $p_i$, הורה צומת $i$ ($0 \leq p_i < i$).
• שורות $N+1..N+M$: שורה $N+i$ מתארת את הרצף ה־$i$ שאינו מופיע. היא מכילה $v_i$ ו־$s_i$ ברווח ביניהם. $v_i$ צומת ההתחלה, ו־$s_i$ מחרוזת של 5 ספרות שאינה מופיעה החל ב־$v_i$ כלפי מעלה. מובטח שהשורש לפחות 4 צעדים מעל $v_i$.

פלט

• שורה $1$: שלם אחד, מספר התצורות שנפסלו מודולו 1234567.

דוגמאות

קלט 1

6 2
0
1
2
3
3
4 01234
5 91234

פלט 1

19

מחבר הבעיה: Jacob Steinhardt, 2014