"In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals" (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)

In the other words, CNF is a formula of type
$(v_{11} \vee v_{12} \vee \ldots \vee v_{1k_1}) \wedge (v_{21} \vee v_{22} \vee \ldots \vee v_{2k_2}) \wedge \ldots \wedge (v_{n1} \vee v_{n2} \vee \ldots \vee v_{nk_n})$, where $\wedge$ represents a logical "AND" (conjunction), $\vee$ represents a logical "OR" (disjunction), and $v_{ij}$ are some boolean variables or their negations. Each statement in brackets is called a clause, and $v_{ij}$ are called literals.

The problem of determining values of variables where the CNF value is true is CNF-SAT. In this problem you have solve a special case of CNF-SAT, called Lucky-SAT. In Lucky-SAT each clause has exactly $7$ literals and literals in each clause are distinct.

Input

The first line contains integers $n$ and $m$, the number of clauses and the number of variables.

The next $n$ lines each contain the description of each clause. The $i$th line contains $7$ integers, $v_{i1}, \ldots , v_{i7}$, the literals of the $i$th clause. If literal $v_{ij} < 0$, it is the negation of variable $-v_{ij}$ and if $v_{ij} > 0$ it is the variable $v_{ij}$.

Output

If there exists a variable assignment such that CNF value is true, output SAT in the first line and a string of length $m$ consisting of zeros and ones in the second line. The $i$th character of the string should be 1 if variable $i$ is assigned to true in the solution and 0 if variable $i$ is assigned to false in the solution. You can output any valid solution.

If there is no such variable assignment, output UNSAT

Constraints

• $1 \le n \le 100$
• $7 \le m \le 10000$
• $1 \le |v_{ij}| \le m$

Example

Input:

8 10
4 -8 7 -10 -3 -1 2
-8 3 10 4 2 -5 9
6 4 2 -7 3 -5 8
7 9 -4 -5 3 10 6
5 -8 3 2 -7 -6 -1
-2 -8 -10 -7 -9 -3 -4
1 -9 -7 -2 10 5 4
5 8 -4 10 -3 -6 -9

Output:

SAT
1011110011