Keyboard Queries

Katrín and her friends are university students who attend a seminar every week. At the start of each seminar, the professor splits the students into groups at random. Katrín and her friends dislike random groups. They want to form a group together so they can chat and avoid getting to know the other students.

The professor keeps a secret string $S$ of length $n$ on their computer. This string seeds the random group generation. To generate groups, a program named manager runs on a substring of $S$. Sometimes the professor mistypes and writes manacher instead, which means the substring is a palindrome. Can Katrín use this information to predict the group division?

The string $S$ has $n$ characters over an unknown alphabet. You are given $q$ queries of two types.

• 1 l r: The substring of $S$ from index $l$ through index $r$ is a palindrome.
• 2 a b x y: Determine whether the substring from index $a$ through $b$ equals the substring from index $x$ through $y$, given the information from the previous queries.

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 10^5$, $1 \leq q \leq 2 \cdot 10^5$), the length of the string and the number of queries. Each of the following $q$ lines starts with 1 or 2, the query type.

For type 1, two integers $l$ and $r$ follow ($1 \leq l \leq r \leq n$). For type 2, four integers $a$, $b$, $x$, $y$ follow ($1 \leq a \leq b \leq n$, $1 \leq x \leq y \leq n$).

For each query of the second type, print "Equal" if the two substrings must be equal, "Not equal" if they cannot be equal, and "Unknown" if both are still possible given the information so far.