تسبب الأبقار مشاكل مستمرة بركوب جرار 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$ صعودًا. مضمون أن الجذر أعلى $v_i$ بأربع خطوات على الأقل.

الإخراج

• السطر $1$: عدد صحيح يعطي عدد التكوينات المستبعدة بترديد 1234567.

أمثلة

الإدخال 1

6 2
0
1
2
3
3
4 01234
5 91234

الإخراج 1

19

مؤلف المسألة: Jacob Steinhardt، 2014