当前没有测试数据。

题目描述

对于一个长度为 $n$ 的序列 A，假设序列中的每一个元素为 $a_1,a_2,\cdots,a_n$，如果存在三个数 $x,y,z$，满足 $1<x<y<z<n$，并且 $a_1 < a_2 < \dots < a_x > a_{x+1} > a_{x+2} > \dots > a_{y} < a_{y+1} < a_{y+2} < \dots < a_z > a_{z+1} > \dots > a_n$，我们就认为这个序列时优美的。</p>

换句话说，假设用序列 $a_i$ 表示波形的高度，那么这个序列需要存在两个波峰（较高点）和一个波谷（较低点），他就是优美的。

现在有 $T$ 个不同的序列，问对于每一个序列它是否是优美的。如果是，则输出 TAK；否则输出 NIE。

输入格式

第一行输入两个整数 $T,n$ 分别表示数据组数和每组数据中序列的长度。

接下来有 $T$ 行，每行输入 $n$ 个整数，$a_1,a_2,\cdots,a_n$，表示序列中元素的大小。

输出格式

输出共 $T$ 行，每行输出 TAK 表示该序列是优美的，否则输出 NIE。

样例

2 11
1 2 3 4 3 2 3 4 3 2 1
9 8 7 6 7 8 9 10 9 8 7

TAK
NIE

说明/提示

对于 $20\%$ 的数据，满足 $n \le 50$。

对于 $40\%$ 的数据，满足 $n \le 200$。

对于 $60\%$ 的数据，满足 $n \le 1000$。

对于 $80\%$ 的数据，满足 $n \le 10^5$。

对于 $100\%$ 的数据，满足 $T \le 10, 5\le n \le 3×10^5, 1 \le a_i \le 10^9$ 。