+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ منبع: آزمون نهایی دوم دوره ۲۶ المپیاد کامپیوتر
----------
طبق نظریه‌های یپکاسوالملک تنها $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
```