Dashgame

Dash este un joc video pentru telefoanele mobile, care uneori nu poate fi câștigat nici de către cei mai buni jucători.

Aria de joc are forma unei matrice cu $M$ linii și $N$ coloane, unde $M$ este un număr impar. Liniile matricei sunt numerotate de jos în sus de la $1$ la $M$, iar coloanele matricei sunt numerotate de la stânga la dreapta de la $1$ la $N$. Caracterul pe care jucătorul îl controlează se află la început pe prima coloană, linia din mijloc, și se deplasează spre ultima coloană. În fiecare secundă, acesta se deplasează fie pe direcția dreapta-sus, fie pe direcția dreapta-jos.

• Direcția dreapta-sus: dacă jucătorul se află pe linia $x$ și coloana $y$, el se va deplasa pe linia $x+1$ și coloana $y+1$.
• Direcția dreapta-jos: dacă jucătorul se află pe linia $x$ și coloana $y$, el se va deplasa pe linia $x-1$ și coloana $y+1$.

La începutul jocului, caracterul se deplasează în direcția dreapta-sus și nu își schimbă direcția fără interacțiunea jucătorului. În fiecare secundă, jucătorul are opțiunea de a apăsa pe ecran pentru a schimba direcția caracterului. Când caracterul se deplasează în direcția dreapta-sus și jucătorul apasă pe ecran, caracterul își va schimba direcția în direcția dreapta-jos. Similar, când caracterul se deplasează în direcția dreapta-jos și jucătorul apasă pe ecran, caracterul își va schimba direcția în direcția dreapta-sus.

Pe fiecare coloană există două obstacole: un stâlp în partea inferioară a coloanei și unul în partea superioară. Pentru fiecare stâlp se cunoaște înălțimea. Stâlpul de sus de pe coloana $i$ are înălțimea $a_i$, adică ocupă spațiile din matrice de pe coloana $i$, între liniile $M - a_i + 1$ și $M$. Stâlpul de jos de pe coloana $i$ are înălțimea $b_i$, adică ocupă spațiile din matrice de pe coloana $i$, între liniile $1$ și $b_i$. Odată ce caracterul ajunge pe un spațiu ocupat de un obstacol, jucătorul pierde.

Scopul jucătorului este să ajungă pe ultima coloană, el fiind declarat câștigător dacă reușește.

Cerinţă

Cunoscând dimensiunile ariei de joc, precum și înălțimile stâlpilor :

• Determinați dacă jucătorul poate câștiga jocul, adică dacă poate să ajungă pe ultima coloană fără să se lovească de vreun obstacol.
• Dacă jucătorul poate câștiga, determinați care este numărul minim și cel maxim de apăsări de ecran pe care jucătorul le poate face pentru a câștiga.
• În cazul în care jucătorul pierde, determinați coloana cea mai din dreapta pe care jucătorul se lovește de un obstacol și pierde.

Date de intrare

Pe prima linie a fișierului de intrare dashgame.in se află numerele $N$ și $M$, reprezentând numărul de coloane, respectiv numărul de linii, în această ordine, separate prin spații. Pe linia a doua se află numerele $a_1$, $a_2, \dots, a_{N}$ în această ordine, reprezentând înălțimile stâlpilor de sus, separate prin spații.
Pe a treia linie se află numerele $b_1$, $b_2, \dots, b_{N}$ în această ordine, reprezentând înălțimile stâlpilor de jos, separate prin spații.

Date de ieșire

Pe prima linie a fișierul de ieșire dashgame.out se va afișa mesajul DA, dacă jucătorul poate câștiga jocul, respectiv mesajul NU, dacă nu îl poate câștiga. Dacă jucătorul poate câștiga jocul, pe a doua linie a fișierului se vor afișa, separate prin spațiu, numărul minim și numărul maxim de apăsări de ecran pe care jucătorul le poate face pentru a câștiga jocul. Dacă jucătorul nu poate câștiga, pe a doua linie a fișierului se va afișa coloana cea mai din dreapta pe care caracterul poate face impact cu un obstacol, pierzând jocul.

Restricții și precizări

• Jucătorul poate apăsa o singură dată pe ecran în orice secundă.
• Jucătorul poate apăsa pe ecran și la începutul jocului, când caracterul se află pe prima coloană, pentru a începe jocul mergând în direcția dreapta-jos.
• Jucătorul nu mai poate apăsa pe ecran odată ce ajunge pe ultima coloană deoarece el este deja câștigător.
• Stâlpii aflați pe aceeași coloană se pot suprapune.
• Dacă un stâlp se intersectează cu punctul de unde începe caracterul, adică prima coloană, linia din mijloc, jucătorul pierde imediat.
• Dacă se afişează răspunsul $DA$ şi doar unul dintre numărul minim, respectiv maxim de apăsări pe ecran este corect, atunci se acordă 40% din punctaj.
• $1 \leq N \leq 1\ 000\ 000$.
• $1 \leq M < 1\ 000\ 000\ 000$.
• M este impar.
• $0 \leq a_i \leq M$.
• $0 \leq b_i \leq M$.

Exemplul 1

dashgame.in

5 5
0 1 2 1 0
0 1 2 1 0

dashgame.out

DA
1 4

Explicație

Pentru numărul minim de apăsări, jucătorul poate apăsa pe ecran atunci când caracterul se află pe coloana 2.

Pentru numărul maxim de apăsări, el poate apăsa ecranul când se află pe coloanele 1, 2, 3 și 4.

Exemplul 2

dashgame.in

5 5
0 1 2 1 0
0 1 3 1 0

dashgame.out

NU
3

Explicație

Nu există spațiu liber între cei doi stâlpi de pe coloana 3. Jucătorul pierde când ajunge la coloana 3.

Exemplul 3

dashgame.in

5 5
0 1 2 1 0
0 1 1 3 0

dashgame.out

DA
2 3

Explicație

Pentru numărul minim de apăsări, jucătorul poate apăsa pe ecran atunci când caracterul se află pe coloana 2 și pe coloana 3. Pentru numărul maxim de apăsări, el mai poate apăsa încă o dată ecranul pe coloana 4.