Задача Megacube. Андрій – справжній фанат шоколаду, жити без нього не може. Нещодавно йому подарували величезну квадратну плитку молочного шоколаду в прозорій обгортці, яку він вирішив залишити на найкращий день свого життя, а до тих пір лише уявляти смак, споглядаючи на нього крізь плівку. Та одного ранку, прокинувшись, він виявив, що за ніч миші вигризли деякі частинки шоколадки, залишивши на їх місці порожнини. Трохи засмутившись, Андрій вирішив зробити записи про стан шоколадки. Він уважно подивився на кожен з чотирьох торців шоколадки і для кожного рядку записав, скільки квадратиків вигризли миші від краю до першого вцілілого квадратику (там, де миші вигризли шоколадку наскрізь, Андрій записував -1). Це заняття заспокоїло Андрія, тож він зміг піти до школи без зайвих думок. Однак по поверненню він виявив, що миші не тільки повністю доїли залишки його дорогоцінної шоколадки, а і частково попсували папірець з записами. Тепер він хоче зрозуміти, чи вигризли вони щось важливе, або ж дані вціліли і відповідають якій-небудь справжній шоколадці. Допоможіть йому зробити це, поки він остаточно не втратив жагу до життя!
Технічні умови. Програма Megacube читає з пристрою стандартного введення число T (1 ≤ T ≤ 10) – кількість тестів. Далі слідують рівно T тестів, кожен з яких поданий п’ятьма рядками:
- перший рядок містить N (1 ≤ N ≤ 10000) – розмір шоколадки;
- другий рядок містить N чисел Li (–1 ≤ Li ≤ N) – записи, отримані при дослідженні лівого торця (у порядку від першого до N-го рядка);
- третій рядок містить аналогічну інформацію для правого торця, в такому самому порядку;
- четвертий рядок містить аналогічні дані (у порядку від першого до N-го стовпчика) щодо верхнього торця;
- п’ятий рядок містить аналогічні записи, отримані при дослідженні нижнього торця шоколадки.
Програма виводить на пристрій стандартного виведення у єдиному рядку рівно T літер – відповіді на кожен з тестових прикладів. Це або “Y” (YES), або “N” (NO).
|
Виведення |
Коментар (для першої шоколадки) |
||||||||||
|
2 3 -1 2 0 -1 0 1 2 2 1 0 0 1 3 -1 0 1 -1 2 1 -1 2 -1 1 0 -1 |
YN |
|