• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی دوم دوره ۲۶ المپیاد کامپیوتر

---

طبق نظریه‌های یپکاسوالملک تنها $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$ ‌است. $$2\leq k\leq 50$$ $$1\leq n,q\leq 200\ 000$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۷	$n,q\leq 1000$
۲	۲۰	$k = 2, n,q\leq 100\ 000$
۳	۴۸	$k \leq 5, n,q\leq 100\ 000$
۴	۲۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

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