No tags yet

No tag edit access

F. Little Artem and 2-SAT

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLittle Artem is a very smart programmer. He knows many different difficult algorithms. Recently he has mastered in 2-SAT one.

In computer science, 2-satisfiability (abbreviated as 2-SAT) is the special case of the problem of determining whether a conjunction (logical AND) of disjunctions (logical OR) have a solution, in which all disjunctions consist of no more than two arguments (variables). For the purpose of this problem we consider only 2-SAT formulas where each disjunction consists of exactly two arguments.

Consider the following 2-SAT problem as an example: . Note that there might be negations in 2-SAT formula (like for *x*_{1} and for *x*_{4}).

Artem now tries to solve as many problems with 2-SAT as possible. He found a very interesting one, which he can not solve yet. Of course, he asks you to help him.

The problem is: given two 2-SAT formulas *f* and *g*, determine whether their sets of possible solutions are the same. Otherwise, find any variables assignment *x* such that *f*(*x*) ≠ *g*(*x*).

Input

The first line of the input contains three integers *n*, *m*_{1} and *m*_{2} (1 ≤ *n* ≤ 1000, 1 ≤ *m*_{1}, *m*_{2} ≤ *n*^{2}) — the number of variables, the number of disjunctions in the first formula and the number of disjunctions in the second formula, respectively.

Next *m*_{1} lines contains the description of 2-SAT formula *f*. The description consists of exactly *m*_{1} pairs of integers *x*_{i} ( - *n* ≤ *x*_{i} ≤ *n*, *x*_{i} ≠ 0) each on separate line, where *x*_{i} > 0 corresponds to the variable without negation, while *x*_{i} < 0 corresponds to the variable with negation. Each pair gives a single disjunction. Next *m*_{2} lines contains formula *g* in the similar format.

Output

If both formulas share the same set of solutions, output a single word "SIMILAR" (without quotes). Otherwise output exactly *n* integers *x*_{i} () — any set of values *x* such that *f*(*x*) ≠ *g*(*x*).

Examples

Input

2 1 1

1 2

1 2

Output

SIMILAR

Input

2 1 1

1 2

1 -2

Output

0 0

Note

First sample has two equal formulas, so they are similar by definition.

In second sample if we compute first function with *x*_{1} = 0 and *x*_{2} = 0 we get the result 0, because . But the second formula is 1, because .

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2017 11:01:52 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|