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