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

حل سؤال در بانک سؤالات