طبق نظریه‌های یپکاسوالملک تنها $k$ رنگ در جهان وجود دارد. برای سادگی این رنگ‌ها را با $1$ تا $k$ شماره‌گذاری کنید. او اعتقاد دارد که اگر رنگ $j$ روی رنگ $i$ ریخته شود، رنگ $t_{i,j}$ حاصل می‌شود به طوری‌که $t_{i,j}$ نیز یکی از همان $k$ رنگ است. البته نکته‌ی عجیبی که وجود دارد این است که $t_{i,j}$ لزوما با $t_{j,i}$ برابر نیست. هم‌چنین $t_{i,i}$ لزوما برابر با $i$ نیست.

در امتحان‌های رنگ‌شناسی، او به هر یک از دانش‌آموزان یک پالت $n$ خانه‌ای می‌‌دهد که هر یک از خانه‌هایش با یکی از $k$ رنگ پر شده است. سپس او دو نوع درخواست از دانش‌آموزان دارد:

1. بر روی خانه‌های $i$ام تا $j$ام رنگ $c$ ریخته شود.
2. رنگ‌ خانه‌ی $i$ام چیست؟

برنامه‌ای بنویسید که بتواند پاسخ سوال‌های امتحان رنگ‌شناسی را به درستی بدهد.

در خط اول ورودی دو عدد طبیعی $n$ و $k$، تعداد خانه‌های پالت و تعداد رنگ‌ها، آمده است.

در هر یک از $k$ خط بعدی، $k$ عدد طبیعی آمده است که $j$امین عدد موجود در خط $i$ام از این خطوط، نشان‌دهنده‌ی $t_{i,j}$ (رنگی که بعد از ریختن رنگ $j$ بر روی رنگ $i$ به وجود می‌آید) است.

در خط بعدی $n$ عددی طبیعی آمده است که $i$امین عدد آن نشان‌دهنده‌ی رنگ ابتدایی خانه‌ی $i$ام پالت است.

در خط بعدی ورودی عدد طبیعی $q$، نشان‌دهنده‌ی تعداد درخواست‌های پیکاسوالملک، آمده است.

در هر یک $q$ سطر بعدی یک درخواست آمده است. درخواست‌های نوع اول، شامل یک کاراکتر # و سه عدد طبیعی $i$ و $j$ و $c$ است. درخواست‌های نوع دوم، شامل یک کاراکتر ? و یک عدد طبیعی $i$ ‌است.

در خروجی، پاسخ‌ هر یک از درخواست‌های نوع دوم را در خطی جداگانه چاپ کنید.

• زیرمسئله اول (۷ نمره): $n,q\leq 1000$
• زیرمسئله دوم (۲۰ نمره): $k = 2, n,q\leq 10^5$
• زیرمسئله سوم (۴۸ نمره): $k \leq 5, n,q\leq 10^5$
• زیرمسئله چهارم(۲۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $2\leq k\leq 50$
• $1\leq n,q\leq 2\times 10^5$

• سوال قبل