====== Palette ======


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

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


  - بر روی خانه‌های $i$ام تا $j$ام رنگ $c$ ریخته شود.
  - رنگ‌ خانه‌ی $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$


===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 2 \\ 1 2 \\ 2 1 \\ 1 1 1 1 \\ 6 \\ # 1 3 2 \\ # 2 4 1 \\ ? 1 \\ ? 2 \\ ? 3 \\ ? 4|2 \\ 2 \\ 2 \\ 1|
|5 3 \\ 1 2 3 \\ 1 2 3 \\ 1 2 3 \\ 1 2 3 1 2 \\ 7 \\ # 1 3 1 \\ ? 2 \\ # 3 5 3 \\ ? 2 \\ # 1 4 2 \\ ? 2 \\ ? 5|1 \\ 1 \\ 2 \\ 3|
</WRAP>






  * [[سوال ۲|سوال قبل]]