You have two positive integer arrays $A$ and $B$ of same length $N$. But elements of array $A$ are hidden from you. And you know $A$ is lexicographically greater than $B$. You’ll be given $M$ information about $A$. Each of the $M$ information will be given in this format “$i > j$” or “$i < j$”, which means $A[i]$ is greater or smaller than $A[j]$ respectively (depending on the sign). You have to find the integers of $A$, or determine no such array exists. In case of multiple possible answers, find the lexicographically smallest one among them.

Input Format

There will be multiple test cases, each input will start with an integer $T$, number of test cases.

Second line will contain two integers $N$ and $M$, length of the arrays and number of information about array $A$.

Next line will contain $N$ integers $b_{1}, b_{2}, b_{3},...,b_{n}$ - integers of array $B$.

Each of the next $M$ lines will contain an information about array $A$, either “$i > j$” or “$i < j$”, as described above.

$1 <= T <= 5$

$1 <= N <= 10^5$

$0 <= M <= 10^5$

$1 <= b_{i} <= 10^9$

$1 <= i , j <= N, i \neq j$

Output Format

For each test case, first determine wheather it is possible to find the integers of A. If possible then first print "YES"(without qoutes) and in the second line print N integers $a_{1}, a_{2}, a_{3},...,a_{n}$-integers of array $A$ $(1 <= a_{i} <= 2\cdot10^9)$. If it is impossible to find the integers, only print "NO"(without qoutes).

Addition Information

For 10 points: $1 <= N <= 7$, $0 <= M <= 7$ and $1 <= b_{i} <= 10$.

For full point: Original constraints.