Juggle with Criteria

A permutation $p$ of length $n$ is an arrangement $p = (p_1, p_2, \ldots, p_n)$ that contains each integer from $1$ to $n$ exactly once. Five criteria measure how close a permutation $p$ is to the identity permutation $(1, 2, \ldots, n)$:

• $a(p)$ — the number of inversions in $p$: pairs of indices $(i, j)$ with $i < j$ and $p_i > p_j$.
• $b(p)$ — the number of local inversions in $p$: indices $i$ with $p_i > p_{i+1}$.
• $c(p)$ — the length of the longest increasing subsequence of $p$: a sequence of indices $i_1 < i_2 < \cdots < i_k$ with $p_{i_1} < p_{i_2} < \cdots < p_{i_k}$.
• $d(p)$ — the length of the longest increasing substring of $p$: a contiguous block $p_i < p_{i+1} < \cdots < p_j$.
• $e(p)$ — the number of fixed points of $p$: indices $i$ with $p_i = i$.

We want to show that these criteria can vary independently. For any prescribed combination of relations — for each criterion, whether its value on $p$ is less than, equal to, or greater than its value on $q$ — the goal is a pair of permutations $p$ and $q$ of the same length that realizes exactly that combination.

For each prescribed relation set and a fixed length $l$, decide whether such a pair of permutations of length $l$ exists.

The first line contains two integers $n$ and $l$ — the number of relation sets and the permutation length ($1 \le n \le 243$; $1 \le l \le 1000$).

Each of the next $n$ lines contains one relation set given as five characters. Each character is $\texttt{<}$, $\texttt{=}$, or $\texttt{>}$. In order, they prescribe the desired relation between $a(p)$ and $a(q)$, between $b(p)$ and $b(q)$, between $c(p)$ and $c(q)$, between $d(p)$ and $d(q)$, and between $e(p)$ and $e(q)$.

For each relation set, print $\texttt{Exists}$ if there exist two permutations $p$ and $q$, both of length $l$, that satisfy all five prescribed relations simultaneously; otherwise print $\texttt{Not exists}$.

Print one answer per relation set, in the input order, each on its own line.

All five relations must hold at once for the single pair $(p, q)$.

For example, take $p = (1, 4, 2, 3)$ and $q = (2, 3, 4, 1)$. Then

• $a(p) = 2 < 3 = a(q)$,
• $b(p) = 1 = 1 = b(q)$,
• $c(p) = 3 = 3 = c(q)$,
• $d(p) = 2 < 3 = d(q)$,
• $e(p) = 1 > 0 = e(q)$,

so this pair realizes the relation set $\texttt{<==<>}$ at length $4$.