"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 ith line contains 7 integers, v_{i1}, \ldots , v_{i7}, the literals of the ith 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 ith 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