Problem Description

Vlatko enjoys working with integer arrays.

He has written down two arrays, each containing $N$ elements, where each element is either an integer or a string representing a variable (the string consists only of lowercase letters).

A variable can be replaced by any integer, and the same variable may appear multiple times in both arrays. If this occurs, all occurrences of the variable must be replaced with the same integer.

Vlatko wonders if it is possible to replace all variables with specific integers such that the two arrays become equal. Two arrays are considered equal if all corresponding positions contain the same integers.

Input Format

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

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

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

Each element in the arrays is either:

• A positive integer less than $1000$
• A string of lowercase letters with a length not exceeding $10$, representing a variable.

Output Format

If there is a way to replace the variables such that the two arrays become equal, output DA; otherwise, output NE.

Sample Input and Output

Sample Input #1

3
3 1 2
3 1 x

Sample Output #1

DA

Sample Input #2

4
4 5 iks ipsilon
1 iks 3 iks

Sample Output #2

NE

Sample Input #3

5
x 3 x y 3
x y 2 z 3

Sample Output #3

DA

Notes

Sample 3 Explanation

When $x, y, z$ are replaced with $2, 3, 3$ respectively, both arrays become equal, namely $(2, 3, 2, 3, 3)$.

Data Constraints

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

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

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

Note

This problem's score is set according to the original COCI contest, with a maximum score of $70$.

The problem is translated from COCI2018-2019 CONTEST #1 T2 Zamjena.

见题面 Input 部分

见题面 Output 部分