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

ماتریس طلایی ماتریسی‌‌ست $n \times n$ که اعداد آن صحیح، نامنفی و متمایز باشند.

روی یک ماتریس طلایی می‌توانیم هر یک از عملیات زیر را به تعداد دلخواه انجام دهیم تا به ماتریس جدیدی تبدیل شود.

۱. عمل $A$: دو سطر ماتریس را با هم جابه‌جا کنیم.

۲. عمل $B$: خانه‌های یک سطر را یک واحد شیفت دورانی بدهیم. (یعنی مقدار خانه‌ی $i$ام آن به خانه‌ی $\left(i + 1\right) \mod n$ برود. (به ازای هر $i$ که $0\leq i < n$)

۳. عمل $C$: به تمام خانه‌های ماتریس یک مقدار صحیح و مثبت را اضافه کنیم.

۴. عمل $D$: مقدار تمام خانه‌های ماتریس را به توان ۲ برسانیم.

دقّت کنید که این ۴ عمل به ترتیب ۲ و ۱ و ۱ و صفر پارامتر دارند. پارامترهای دو عمل $A$ و $B$ باید در محدوده‌ی $\left[0, n\right)$ باشند. پارامتر عمل $C$ نیز باید از $1$ تا $10^9$ باشد.

می‌گوییم ماتریس $X$ نوه‌ی ماتریس طلایی $G$ است اگر بتوان با متناهی بار اِعمالِ اَعمال بالا روی $G$ به $X$ رسید.

ماتریس‌های $X$ و $Y$ را نیز پسرخاله می‌نامیم، اگر و فقط اگر ماتریسی مثل $G$ پیدا شود که $X$ و $Y$ نوه‌ی آن باشند.

به ازای $T$ سناریو، دو ماتریس $X$ و $Y$ به شما می‌دهیم، باید بگویید که آیا آن دو پسرخاله هستند یا نه.

ورودی

در سطر اوّل ورودی عدد طبیعی $T$ آمده است.

به ازای هر سناریو: در خط اوّل عدد $n$ آمده است. در $n$ سطر بعدی، در هر سطر $n$ عدد آمده است. عدد $j$ام در سطر $i$ام برابر $X_{i,j}$ خواهد بود. پس از ماتریس $X$، ماتریس $Y$ نیز به همین صورت در $n$ خط بعد از آن خواهد آمد.

اعداد داخل هر سطر با فاصله از هم جدا شده اند.$$1\leq T\leq20$$ $$1\leq n \leq 1\ 000$$

تمام اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود.

هر یک از دو ماتریس هر سناریو طلایی هستند و اعداد داخل هر یک متمایز هستند.

خروجی

به ازای هر سناریو در یک خط باید Yes (در صورتی که دو ماتریس پسرخاله بودند) یا No (در صورتی که دو ماتریس پسرخاله نبودند) بنویسید.

زیرمسئله‌ها

مثال

ورودی نمونه

2
2
1 0
2 3
10 5
1 2
3
10 20 30
1 2 3
9 7 8
1 4 9
100 400 900
49 64 80

خروجی نمونه

Yes
No