Description

Vlatko likes working with arrays of integers.

He wrote down two arrays on paper, each containing $N$ elements. Each element is either an integer, or a string representing a variable (the string contains only lowercase letters).

A variable can be replaced by any integer, and the same variable may appear multiple times in the two arrays. If this happens, then during replacement, all positions where the variable appears must be replaced by the same integer.

Vlatko wonders whether it is possible to replace all variables with specific integers so that the two arrays become equal. Two arrays are equal if the integers at all corresponding positions are equal.

Input Format

The first line contains a positive integer $N$, the number of elements in each array.

The second line contains the $N$ elements of the first array.

The third line contains the $N$ elements of the second array.

Each element in the arrays is one of the following:

• A positive integer less than $1000$.
• A string of length at most $10$ containing only lowercase letters, representing a variable.

Output Format

If there exists a way to make the two arrays equal after replacement, output DA; otherwise, output NE.

3
3 1 2
3 1 x

DA

4
4 5 iks ipsilon
1 iks 3 iks

NE

5
x 3 x y 3
x y 2 z 3

DA

Hint

Explanation for Sample 3

When replacing $x, y, z$ with $2, 3, 3$ respectively, the two arrays become equal, both being $(2,3,2,3,3)$.

Constraints

For $20\%$ of the testdata, each variable appears only once in the two arrays.

For another $20\%$ of the testdata, the arrays contain only two variables $x, y$.

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4$.

Note

The score of this problem follows the original COCI setting, with a full score of $70$.

Translated from COCI2018-2019 CONTEST #1 T2 Zamjena.

Translated by ChatGPT 5