Сізге өлшемі $n \times n$ болатын тақта берілген, оның $n^2$ ұяшығының әрқайсысында $-1$, $0$ немесе $1$ сандарының бірі жазылған. Сондай-ақ төрт бүтін сан $A_L, A_D, A_R$ және $A_U$ берілген. Біз екі сынық сызық жүргізгіміз келеді:
- біріншісі тақтаның сол жақ жоғарғы бұрышын оң жақ төменгі бұрышымен қосады және ұяшықтардың шекаралары бойымен тек оңға және төмен қарай жүреді,
- ал екіншісі тақтаның сол жақ төменгі бұрышын оң жақ жоғарғы бұрышымен қосады және тек оңға және жоғары қарай жүреді.
Екі сынық сызық тақтаны төрт (бос болуы мүмкін) аймаққа бөледі: сол, төменгі, оң және жоғарғы. Осы төрт аймақтағы ұяшықтардың қосындысы сәйкесінше $A_L, A_D, A_R$ және $A_U$ сандарына тең болатындай екі сынық сызықтың бар-жоғын тексеріңіз. Тәуелсіз $t$ тесттің әрқайсысы үшін TAK (иә) немесе NIE (жоқ) деп шығарыңыз.
Суреттерде мысалдағы бірдей $5 \times 5$ тақта көрсетілген.
Сол жақтағы суретте қосындылары $(1, 0, -2, 1)$ ($A_L, A_D, A_R, A_U$ ретімен) болатын аймақтарға бөлу көрсетілген. Бірінші сынық сызықты RDDDRRDRDR сөзімен, ал екіншісін RURUURRUUR сөзімен сипаттауға болады (мұндағы D, U және R сәйкесінше шекаралар бойымен төмен, жоғары және оңға жылжуды білдіреді). Мысалы, оң жақ аймақта қосындысы $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$ болатын 8 ұяшық бар.
Оң жақтағы суретте қосындылары $(0, 2, -3, 1)$ болатын аймақтарға бөлу көрсетілген. Сол жақ аймақ бос, сондықтан оның ұяшықтарының қосындысы нөлге тең. Сынық сызықтарды DRRRRDDRDD және UUUURURRRR сөздерімен сипаттауға болады.
Дәл осы тақтаны қосындылары $(-2, 0, 1, 1)$, яғни $A_L = -2, A_D = 0, A_R = 1, A_U = 1$ болатын аймақтарға бөлу мүмкін емес. Сол жақтағы суретте дәл осы мәндер басқа ретпен кездесетініне назар аударыңыз — реттің маңызы бар.
Кіріс деректер
Кіріс деректердің бірінші жолында тесттер санын білдіретін бір бүтін сан $t$ ($1 \le t \le 100\,000$) берілген.
Әрбір тесттің бірінші жолында тақта қабырғасының ұзындығын және төрт аймақтың қажетті қосындыларын білдіретін бес бүтін сан $n, A_L, A_D, A_R, A_U$ ($1 \le n \le 2000; -n^2 \le A_L, A_D, A_R, A_U \le n^2$) берілген.
Тесттің келесі $n$ жолының әрқайсысы тақтаны сипаттайды; $i$-ші жолда тақтаның $i$-ші қатарын сипаттайтын $n$ бүтін сан $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$) берілген. Тақтадағы барлық сандардың жалпы қосындысы $A_L + A_D + A_R + A_U$ мәніне тең.
Барлық тесттер бойынша $n^2$ мәндерінің жалпы қосындысы $4\,000\,000$-нан аспайды.
Шығыс деректер
Дәл $t$ жол шығарыңыз — әрбір тест үшін, егер тақтаны көрсетілген қосындылары бар аймақтарға бөлетін сынық сызықтар бар болса, TAK (иә) сөзін, әйтпесе NIE (жоқ) сөзін шығарыңыз.
Мысал
Кіріс деректер
5 5 1 0 -2 1 1 0 -1 0 0 1 0 0 1 -1 0 1 -1 0 -1 0 0 0 0 1 -1 0 0 0 0 5 0 2 -3 1 1 0 -1 0 0 1 0 0 1 -1 0 1 -1 0 -1 0 0 0 0 1 -1 0 0 0 0 5 -2 0 1 1 1 0 -1 0 0 1 0 0 1 -1 0 1 -1 0 -1 0 0 0 0 1 -1 0 0 0 0 2 1 -1 0 1 1 0 -1 1 1 0 0 0 0 0
Шығыс деректер
TAK TAK NIE NIE TAK
Ескертпе
Алғашқы үш тест есеп шартында көрсетілген мысалдарға сәйкес келеді. Оларда бірдей тақта және ретімен $(A_L, A_D, A_R, A_U)$ қосындыларына сұраныстар берілген:
- $(1, 0, -2, 1)$, жауабы
TAK - $(0, 2, -3, 1)$, жауабы
TAK - $(-2, 0, 1, 1)$, жауабы
NIE