Hide

Problem A
Av(1324)

Languages en is

Five problems ready, and already Arnar and Atli are running out of ideas. In desperation they start asking other members of the faculty at RU what problems they should pose for their students, and after a bit of searching they end up talking to Henning. He says that “Pattern avoiding permutations” are what they’re looking for. He says that there is nothing more interesting than solving the problem of how many permutations avoid the pattern $1324$. “Isn’t this a bit tough for the students? This is an unsolved problem!” Arnar says. After a bit of discussion a conclusion was reached, instead of having the students solve this unsolved problem, they only have to check whether a particular permutation avoids the pattern.

That is where you come in! The input gives you a permutation $\pi _1, \pi _2, \dots , \pi _ n$ of the numbers $1, 2, \dots , n$. This means the numbers $\pi _1, \pi _2, \dots , \pi _ n$ are the numbers $1, 2, \dots , n$, just possibly in a different order. Determining whether the pattern $1324$ appears is achieved by checking whether there exist indices $1 \leq i_1 < i_2 < i_3 < i_4 \leq n$ such that $\pi _{i_1} < \pi _{i_3} < \pi _{i_2} < \pi _{i_4}$.

Input

The first line of the input contains an integer $1 \leq q \leq 10^5$, the number of permutations in the input. Next there are $2q$ lines, each two lines giving one permutation. The first of the two lines contains a single integer $n_ i$, the size of the permutation. The second contains the permutation $1 \leq \pi _1, \pi _2, \dots , \pi _ n \leq n_ i$, with the numbers separated by spaces. Let $n$ be the sum of the sizes of all the permutations in the input. It is guaranteed that $n \leq 10^6$.

Output

For each permutation in the input, print a single line. If the pattern does not appear, print "Ekkert mynstur!". Otherwise print indices $1 \leq i_1 < i_2 < i_3< i_4 \leq n$ such that $\pi _{i_1} < \pi _{i_3} < \pi _{i_2} < \pi _{i_4}$, separating the indices by spaces. If there are several such sets of indices, any one of them will be accepted.

Scoring

Group

Points

Constraints

1

20

$1 \leq n_ i \leq 4$

2

20

$1 \leq n_ i \leq 20$

3

25

$1 \leq n_ i \leq 60$

4

25

$1 \leq n_ i \leq 2000$

5

10

$1 \leq n_ i \leq 10^6$

Sample Input 1 Sample Output 1
4
4
1 2 3 4
4
1 3 2 4
10
3 4 2 5 1 6 7 8 10 9
10
8 5 7 2 9 6 3 4 1 10
Ekkert mynstur!
1 2 3 4
Ekkert mynstur!
2 3 6 10