Experimente2

NOTE: The translation may not reflect the original text verbatim.

Following the experiments carried out in the month in which the County Olympiad of Informatics was held, Dexter decided to protect at all costs the discoveries he had made regarding a cure for cancer. He therefore chose to implement homomorphic encryption, a special method that allows logical operations to be performed directly on encrypted data without decrypting it.

Convinced that this type of encryption will ensure the confidentiality of his discoveries, Dexter is preparing to send to his nanotechnology professor the $Q$ chapters of his scientific work, entitled From experiments to experiments.
In each chapter, he represents the collection of the experimental data as a sequence of $n$ non-negative integers, arranged either linearly (in a line) or circularly (in a ring).

Before sending the data, Dexter thinks he has noticed an unusual phenomenon whilst analysing the homomorphic encryption: if, in either a linear or a circular structure, the sequence reaches a uniform state, that is to say, all values in the sequence become equal, by repeatedly replacing two adjacent elements with their exclusive disjunction—i.e., a logical operation called xor, often denoted by $\oplus$; in C/C++ it is written as the $\wedge{}$ operator—, then an unforeseen problem may arise: encryption algorithms can no longer distinguish between encrypted data, and direct computations on it become useless.

For instance, if a chapter consists of $n=4$ integers arranged linearly, $(4,4,1,5)$, and we choose the first two elements and replace them with their exclusive disjunction, we obtain $(4\oplus4,1,5)=(0,1,5)$. Whatever adjacent pair we next choose, we can never obtain a uniform sequence, because
$(0\oplus1,5)=(1,5)$ and $(0,1\oplus5)=(0,4)$.

Instead, should we choose, for the same initial sequence, the last two elements and replace them with their exclusive disjunction, we get $(4,4,1\oplus5)=(4,4,4)$, which is a uniform sequence.

Task

For each of the $Q$ chapters, determine whether the sequence of the $n$ non-negative integers can be transformed into a uniform state—with at least two values remaining in the sequence—by repeatedly (as many times as necessary) replacing two adjacent elements with their exclusive disjunction.

Input data

The file experimente2.in contains on the first line two values:

• $C$, which is $1$ if the values are considered to be arranged linearly, or $2$ if they are considered to be arranged circularly;
• $Q$, a natural number indicating the number of chapters Dexter wishes to analyse.

Each of the next $Q$ chapters is described by:

• one line containing the number $n$, the length of the sequence;
• one line with the $n$ non-negative integers, separated by spaces, representing the sequence values.

Output data

The file experimente2.out must contain, for every chapter—in the order given in the input—a single line with:

• the text DA, if there exists a sequence of replacements that leaves at least two values in the sequence and all remaining values equal, or
• the text NU, otherwise.

Constraints and clarifications

• $2 \le n \le 200 \ 000$;
• $1 \le Q \le 25$;
• $C \in \{1,2\}$;
• every element of every sequence belongs to $\{0,1,\dots,2\cdot10^9\}$;
• the sum of all $n$ over all $Q$ chapters does not exceed $1 \ 000 \ 000$;
• the exclusive disjunction is the xor operation.

Example 1

experimente2.in

1 2
6
1 1 0 0 1 1
4
2 4 8 32

experimente2.out

DA
NU

Explanation

We have $C=1$, therefore the values are arranged linearly.

One possible sequence of operations is to replace the first two and the last two elements with their exclusive disjunction, obtaining $(1\oplus1,0,0,1\oplus1)=(0,0,0,0)$, which is a uniform sequence.

For the sequence $(2,4,8,32)$ there is no way to reach a uniform state.

Example 2

experimente2.in

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

experimente2.out

DA
DA

Explanation

We have $C=2$, therefore the values are arranged circularly.

For the first chapter, we can replace the first and last elements with their exclusive disjunction (since they are adjacent on the circle), yielding $(3\oplus2,1,1,1)=(1,1,1,1)$.

For the second chapter, we may successively replace the first two elements with their exclusive disjunction, obtaining $((1\oplus2)\oplus4,7,7,7)=(7,7,7,7)$.