Овај задатак је поновљен у циљу увежбавања различитих техника решавања.

Дат је низ који садржи природне бројеве и цео број \(D\). Напиши програм који одређује који се од неколико датих низова може од полазног добити разменама елемената који су тачно на растојању \(D\).

Улаз

Са стандардног улаза се учитава цео број \(d\) (\(1 \leq d \leq k\)), затим цео број \(k\) (\(5 \leq k \leq 10^5\)), затим цео број \(n\) (\(1 \leq n \leq 10\)) и након тога \(n\) низова дужине \(k\) чији су елементи раздвојени размацима.

Излаз

На стандардни излаз за сваки низ од другог до последњег исписати da ако се може трансформисати у први разменама елемената на растојању \(d\), тј. ne у супротном.

Пример

Улаз

2
7
6
1 2 3 4 5 6 7
3 4 1 2 7 6 5
2 1 4 3 6 5 7
1 4 7 2 3 6 5
1 4 7 6 3 2 5
5 4 7 6 3 1 2

Излаз

da
ne
da
da
ne

Објашњење

3 4 1 2 7 6 5   - razmena 3 i 1, 4 i 2, i 7 i 5
2 1 4 3 6 5 7   - ne može
1 4 7 2 3 6 5   - razmena 4 i 2, 7 i 3 i 7 i 5
1 4 7 6 3 2 5   - razmena 6 i 2, 4 i 2, 7 i 3 i 7 i 5
5 4 7 6 3 1 2   - ne može