نقل است شیخ در پایان عمر خویش، تصمیم بر فارغ‌التحصیل کردن مریدان و اعطای مدرک به آن‌ها می‌گیرد. از این رو $p$ مرید خود را فراخوانده و از آن‌ها می‌خواهد ابتدا $n$ اتاق در یک ردیف بسازند، به طوری که اتاق $i$ام با یک در به اتاق $i-1$ راه داشته باشد. پس از ساخت و ساز، شیخ به درون اتاق‌ها رفته، روی هر یک از این درها یک کلمه می‌نویسد و تمام آن‌ها را می‌بندد.

شیخ در ادامه افزود: »ای مریدان! هر یک از شما بر اساس مرتبهٔ خود به اتاق $e_i$ وارد شود. برای گذر از یک در و سیر و سلوک عرفانی، باید کلمه‌ی روی در را با جان و دل درک کنید. بعضی از شما موفق می‌شوید به انتها رسیده و از اتاق $1$ خارج شوید، در حالی که بعضی دیگر در میان راه متوقف شده و دیگر نمی‌توانید ادامه دهید. باشد که در راه رسیدن به مرتبه‌ی نهایی، از هیچ مشارکتی فروگذار نکنید.»

ما می‌دانیم که هر مرید از آموخته‌های قبلی، از کلماتی درک سطحی پیدا کرده است. هر مرید برای گذشتن از یک در لازم است از کلمه‌ی روی در، درک سطحی داشته باشد و پس از گذشتن از آن، درک او عمیق می‌شود. هم‌چنین، هر مرید با کسب درک عمیق از یک کلمه، جلسه‌ی درس با محوریت آن کلمه تشکیل می‌دهد. پس از این جلسه، تمام مریدان دیگر از آن کلمه‌یک درک سطحی پیدا خواهند کرد. علاوه بر این، لزوماً تمام کلماتی که مریدان از گذشته می‌دانند توسط شیخ استفاده نشده است. دقت کنید که درک به دست آمده از دست نمی‌رود.

مریدان خیلی زود به مرتبه‌ی نهایی خود رسیدند اما شیخ پیش از آن که بتواند مدرک مریدان را صادر کند، دار فانی را وداع گفت. مریدان نعره‌ها زدند و از بی‌مدرکی سر به بیابان گذاشتند.

برنامه‌ای بنویسید که با دریافت اطلاعات موجود در اسناد تاریخی، مرتبه‌ی نهایی تمام مریدان را به دست آورد.

• خطوط ورودی به صورت زیر هستند:
  • $n\ \ p\ \ k$: تعداد اتاق‌ها $n$، تعداد مریدان $p$ و تعداد زوج‌های مرید-کلمه که در انتها می‌آیند.
  • $w_1\ldots w_n$: کلمات روی درها شامل $n$ کلمه که با فاصله از هم جدا شده‌اند.
  • $e_1\dots e_p$: عدد $e_i$ مرتبه‌ی مرید $i$ ام و شماره‌ی اتاق شروع او است.
  • $k$ خط به صورت: $s_j \ v_j$ به این معنی که مرید $s_j$ از کلمه‌ی $v_j$ درک سطحی دارد.
• $w_i, v_j$: کلماتی حداکثر ۱۰ حرفی متشکل از حروف کوچک الفبای انگلیسی هستند.
• در ۴۰ درصد تست‌ها $n\times p \leq 10^7$ می‌باشد.
• در تمام تست‌ها: $1\leq n, p\leq 10^5$، $1\leq k\leq 10^6$، $0\leq e_i \leq n$ و $1\leq s_j \leq p$.

خروجی تنها شامل یک خط به شکل زیر است:

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت