Мирлинд и Влора живеат во мало градче кое може да се претстави како правоаголна шема од квадратчиња (полиња), и тоа N редици со по M квадратчиња. Секое квадратче (поле) на влез се претставува преку еден знак, при што:
‘.’ означува проодно поле
‘#’ означува ограда
‘M’ ја означува куќата на Мирлинд
‘V’ ја означува куќата на Влора

Мирлинд сака да отиде на гости кај Влора. Тој може да се движи од едно проодно поле во друго само доколку тие две полиња делат заедничка страна. Мирлинд не може да се придвижи во поле во кое што има ограда.

Бидејќи може да се случи да не може да се стигне од куќата на Мирлинд до куќата на Влора заради оградите кои се многу високи, Мирлинд смислил решение:
Тој може да ископа точно еден тунел, од кое било поле со координати (А, B) до кое било друго поле со координати (X, Y) доколку е задоволен условот |A-X| + |B-Y| ≤ K и притоа двете полиња (A, B) и (X, Y) се проодни. Со други зборови, Мирлинд има сила да ископа точно еден тунел, и тој тунел може да почнува во едно проодно поле и да завршува во друго проодно поле, при што тие две полиња се на растојание најмногу K.

Забелешка: Полињата во кои се наоѓаат куќите на Мирлинд и Влора се сметаат за проодни и можно е во тие полиња да почне или да заврши еден тунел.

За дадена правоаголна шема, пресметајте дали може да се стигне од куќата на Мирлинд до куќата на Влора според дадените правила.

Влез

Во првиот ред е дадена големината на градчето: два броја N и M (2 ≤ N, M ≤ 1000), разделени со едно празно место.
Во вториот ред даден е еден цел број K (0 ≤ K < 4000).
Во следните N редови се дадени по M знаци кои го опишуваат градчето, според објаснувањето дадено во текстот на задачата.
Загарантирано е дека ќе биде присутно точно едно ‘M’ и точно едно ‘V’ во влезот.

Забелешка:
За 30% од поените ќе важи: K = 0. Со други зборови, за овие поени ја решавате задачата занемарувајќи ја опцијата за тунел.
За дополнителни 30% од поените ќе важи: 2 ≤ N, M ≤ 100

Излез

Во еден ред отпечатете “DA” доколку може да се стигне од куќата на Мирлинд до куќата на Влора, и “NE” во спротивно.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
3 3
0
.M.
##.
..V

излез
DA

влез
3 3
1
M..
###
..V

излез
NE

влез
3 3
2
M..
###
..V

излез
DA