Little 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: <image>. Note that there might be negations in 2-SAT formula (like for x1 and for x4).

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, m1 and m2 (1 ≤ n ≤ 1000, 1 ≤ m1, m2 ≤ n2) — the number of variables, the number of disjunctions in the first formula and the number of disjunctions in the second formula, respectively.

Next m1 lines contains the description of 2-SAT formula f. The description consists of exactly m1 pairs of integers xi ( - n ≤ xi ≤ n, xi ≠ 0) each on separate line, where xi > 0 corresponds to the variable without negation, while xi < 0 corresponds to the variable with negation. Each pair gives a single disjunction. Next m2 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 xi (<image>) — 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 x1 = 0 and x2 = 0 we get the result 0, because <image>. But the second formula is 1, because <image>.
#include <bits/stdc++.h>
using namespace std;
int n, m1, m2;
pair<int, int> e1[1111111], e2[1111111];
int convert(int x) {
  if (x > 0) return x - 1;
  if (x < 0) return -x - 1 + n;
}
struct Graph {
  Graph() { memset(g, 0, sizeof g); }
  void addEdge(int x, int y) {
    x = convert(x);
    y = convert(y);
    g[(x + n) % (2 * n)][y] = 1;
    g[(y + n) % (2 * n)][x] = 1;
    bs[(x + n) % (2 * n)][y] = true;
    bs[(y + n) % (2 * n)][x] = true;
  }
  bool g[2222][2222];
  bool used[2222];
  void dfs1(int ver) {
    used[ver] = true;
    for (int i = (0); i < (2 * n); i++)
      if (!used[i] && g[ver][i]) dfs1(i);
    order.push_back(ver);
  }
  void dfs2(int ver) {
    used[ver] = true;
    component.push_back(ver);
    for (int i = (0); i < (2 * n); i++)
      if (!used[i] && g[i][ver]) dfs2(i);
  }
  bool issolvable() {
    memset(used, 0, sizeof used);
    for (int i = (0); i < (2 * n); i++)
      if (!used[i]) dfs1(i);
    memset(used, 0, sizeof used);
    for (int i = (0); i < (2 * n); i++) {
      int v = order[2 * n - 1 - i];
      if (!used[v]) {
        dfs2(v);
        allc.push_back(component);
        component.clear();
      }
    }
    memset(cid, 0, sizeof cid);
    for (int i = (0); i < (allc.size()); i++)
      for (int j = (0); j < (allc[i].size()); j++) cid[allc[i][j]] = i;
    for (int i = (0); i < (n); i++)
      if (cid[i] == cid[i + n]) return false;
    return true;
  }
  bitset<2000> bs[2000];
  void printsolution() {
    for (int i = (0); i < (n); i++) {
      if (i) printf(" ");
      printf("%d", (cid[i] > cid[i + n]) ? 1 : 0);
    }
    puts("");
  }
  void psol(int ver) {
    for (int i = (0); i < (n); i++) {
      if (i) printf(" ");
      if (bs[ver][i])
        printf("1");
      else if (bs[ver][i + n])
        printf("0");
      else
        printf("%d", (cid[i] > cid[i + n]) ? 1 : 0);
    }
    puts("");
  }
  void psol(int ver, int ver2) {
    for (int i = (0); i < (n); i++) {
      if (i) printf(" ");
      if (bs[ver][i])
        printf("1");
      else if (bs[ver][i + n])
        printf("0");
      else if (bs[ver2][i])
        printf("1");
      else if (bs[ver2][i + n])
        printf("0");
      else
        printf("%d", (cid[i] > cid[i + n]) ? 1 : 0);
    }
    puts("");
  }
  int cid[2222];
  vector<vector<int> > allc;
  vector<int> order, component;
  void dfs3(int ver) {
    used[ver] = true;
    bs[ver][ver] = true;
    for (int i = (0); i < (2 * n); i++)
      if (g[ver][i]) {
        if (!used[i]) dfs3(i);
        bs[ver] |= bs[i];
      }
  }
  void findc() {
    memset(used, 0, sizeof used);
    for (int i = (0); i < (2 * n); i++)
      if (!used[i]) dfs3(i);
  }
};
bool isbad(bitset<2000> bs) {
  for (int i = (0); i < (n); i++)
    if (bs[i] && bs[i + n]) return true;
  return false;
}
Graph g1, g2;
int main() {
  cin >> n >> m1 >> m2;
  for (int i = (0); i < (m1); i++) scanf("%d %d", &e1[i].first, &e1[i].second);
  for (int i = (0); i < (m2); i++) scanf("%d %d", &e2[i].first, &e2[i].second);
  for (int i = (0); i < (m1); i++) g1.addEdge(e1[i].first, e1[i].second);
  for (int i = (0); i < (m2); i++) g2.addEdge(e2[i].first, e2[i].second);
  bool is1 = g1.issolvable();
  bool is2 = g2.issolvable();
  if (is1 && is2) {
    g1.findc();
    g2.findc();
    for (int i = (0); i < (2 * n); i++)
      if (g1.bs[i] != g2.bs[i]) {
        if (isbad(g1.bs[i]) && isbad(g2.bs[i])) continue;
        if (isbad(g1.bs[i])) {
          g2.psol(i);
          return 0;
        } else if (isbad(g2.bs[i])) {
          g1.psol(i);
          return 0;
        } else {
          for (int j = (0); j < (2 * n); j++)
            if (g1.bs[i][j] != g2.bs[i][j]) {
              if (g1.bs[i][j]) {
                if (isbad(g2.bs[(j + n) % (2 * n)])) continue;
                g2.psol(i, (j + n) % (2 * n));
                return 0;
              } else if (g2.bs[i][j]) {
                if (isbad(g1.bs[(j + n) % (2 * n)])) continue;
                g1.psol(i, (j + n) % (2 * n));
                return 0;
              }
            }
        }
      }
    puts("SIMILAR");
  } else if (is1) {
    g1.printsolution();
  } else if (is2) {
    g2.printsolution();
  } else {
    puts("SIMILAR");
  }
  return 0;
}
