#include <bits/stdc++.h>
using namespace std;
struct point {
  long double x, y;
  point() {
    x = 0;
    y = 0;
  }
  point(long long a, long long b) {
    x = a;
    y = b;
  }
  bool operator==(const point &b) { return x == b.x and y == b.y; }
  bool operator>(const point &b) {
    if (x > b.x) return true;
    if (x < b.x) return false;
    if (x == b.x) {
      if (y < b.y) return false;
      if (y > b.y) return true;
      return true;
    }
  }
  bool operator<(point &b) { return (b > point(x, y)); }
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist(point b) {
    return sqrt((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  long double dist_kv(point b) {
    return ((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  bool point_on_sig(point &a, point &b) {
    return abs(a.dist(b) - (dist(a) + dist(b))) <= 1e-6;
  }
  long double polar_angle() {
    long double alpha = atan2(y, x);
    long double pi = 3.141592654;
    if (alpha < 0) alpha += 2 * pi;
    return alpha;
  }
};
struct line {
  long double A, B, C;
  line() {
    A = 0;
    B = 0;
    C = 0;
  }
  line(point &a, point &b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = -A * a.x - B * a.y;
  }
  line(long double a, long double b, long double c) {
    A = a;
    B = b;
    C = c;
  }
  line line_perp_dan_cherez_point(point a) {
    return line(-B, A, -(A * a.y) + B * a.x);
  }
  bool onli(point a) { return A * a.x + B * a.y + C == 0; }
  point intersect_lines(line &a) {
    point p;
    p.x = -(((C * a.B) - (a.C * B)) / ((A * a.B) - (a.A * B)));
    p.y = -(((A * a.C) - (a.A * C)) / ((A * a.B) - (a.A * B)));
    return p;
  }
  bool intersect(line &b) { return A * b.B - B * b.A != 0; }
  bool operator==(line &a) { return A == a.A && B == a.B && C == a.C; }
  long double distance_perpendicular(point &d) {
    return abs(A * d.x + B * d.y + C) / (sqrt(A * A + B * B));
  }
};
struct vc {
  long double x, y;
  vc() {
    x = 0;
    y = 0;
  }
  vc(long double x_, long double y_) {
    x = x_;
    y = y_;
  }
  vc(const point &a) {
    x = a.x;
    y = a.y;
  }
  vc minus(const vc &b) { return vc(x - b.x, y - b.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double scalar(const vc &b) { return x * b.x + y * b.y; }
  long double vector(const vc &b) { return x * b.y - y * b.x; }
  long double angle(const vc &b) { return atan2(vector(b), scalar(b)); }
};
vector<int> top;
void top_sort(int v, vector<int> nodes[], int used[], int colors[]) {
  if (colors[v] == 1) {
    cout << -1;
    exit(0);
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (used[nodes[v][i]] == 0) top_sort(nodes[v][i], nodes, used, colors);
  }
  top.push_back(v + 1);
  used[v] = 1;
  colors[v] = 2;
}
vector<int> z_function(string s) {
  vector<int> z(s.size());
  for (int i = 1, l = 0, r = 0; i < s.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
vector<int> p_function(string s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}
vector<int> now_ans;
void dfsik(int v, vector<int> nodes[], int colors[], int turn) {
  if (colors[v] == 1) {
    now_ans.push_back(0);
    return;
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (turn == 1)
      dfsik(nodes[v][i], nodes, colors, 2);
    else
      dfsik(nodes[v][i], nodes, colors, 1);
  }
  if (nodes[v].empty()) {
    now_ans.push_back(turn);
    return;
  }
  colors[v] = 2;
}
long long t[8 * 100000];
long long t1[8 * 100000];
long long a[8 * 100000];
void push(long long v, long long l, long long r) {
  if (a[v] == 0) return;
  if (l != r) {
    a[v * 2] += a[v];
    a[v * 2 + 1] += a[v];
  }
  t[v] += a[v] * (r - l + 1);
  t1[v] += a[v];
  a[v] = 0;
}
void build(long long a[], long long v, long long tl, long long tr) {
  if (tl == tr) {
    t[v] = a[tl];
    t1[v] = a[tl];
  } else {
    long long tmtm = (tl + tr) / 2;
    build(a, v * 2, tl, tmtm);
    build(a, v * 2 + 1, tmtm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
    t1[v] = max(t1[v * 2], t1[v * 2 + 1]);
  }
}
long long sum(long long v, long long tl, long long tr, long long l, long long r,
              long long num) {
  if (l > r) return 0;
  push(v, tl, tr);
  if (l == tl && r == tr) {
    t[v] += num;
    t1[v] += num;
    return t[v];
  }
  if (l <= tl and tr <= r) {
    a[v] += num;
    push(v, tl, tr);
    return t[v];
  }
  long long tmtm = (tl + tr) / 2;
  return (sum(v * 2, tl, tmtm, l, min(r, tmtm), num) +
          sum(v * 2 + 1, tmtm + 1, tr, max(l, tmtm + 1), r, num));
}
long long maxim(long long v, long long tl, long long tr, long long l,
                long long r) {
  if (l > r) return -LONG_LONG_MAX;
  push(v, tl, tr);
  if (l == tl && r == tr) return t1[v];
  long long tmtm = (tl + tr) / 2;
  return max(maxim(v * 2, tl, tmtm, l, min(r, tmtm)),
             maxim(v * 2 + 1, tmtm + 1, tr, max(l, tmtm + 1), r));
}
void sett(long long v, long long idx, long long x, long long l, long long r) {
  if (l == r) {
    t[v] = x;
    t1[v] = x;
    return;
  }
  long long m = (l + r) >> 1;
  if (l <= idx and m >= idx) {
    sett(2 * v, idx, x, l, m);
  } else
    sett(2 * v + 1, idx, x, m + 1, r);
  t[v] = min(t[2 * v], t[2 * v + 1]);
  t1[v] = max(t1[2 * v], t1[2 * v + 1]);
}
int parents[500000];
void create(int v) { parents[v] = v; }
int find_parent(int v) {
  if (v == parents[v]) return v;
  return parents[v] = find_parent(parents[v]);
}
void join(int a, int b) {
  int x = find_parent(a);
  int y = find_parent(b);
  if (x != y) {
    parents[x] = y;
  }
}
vector<long long> manac(string s, int shift) {
  long long l = 0;
  long long r = -1;
  long long n = s.size();
  vector<long long> ans(n);
  for (int i = 1; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i + shift, ans[r - i + l + shift]);
    }
    while (i - k - 1 >= 0 && i + k + 1 - shift < n &&
           s[i - k - 1] == s[i + k + 1 - shift]) {
      k++;
    }
    if (i + k - shift > r) {
      l = i - k;
      r = i + k - shift;
    }
    ans[i] = k;
  }
  return ans;
}
long long INF = (long long)1e20;
vector<int> dividers(int x) {
  vector<int> ans;
  ans.push_back(x);
  for (int i = 2; i <= sqrt(x); ++i) {
    if (x % i == 0) {
      ans.push_back(i);
      if (i != sqrt(x)) ans.push_back(x / i);
    }
  }
  return ans;
}
long long max_arr(long long arr[], long long n) {
  long long maxi = -INF;
  for (int i = 0; i < n; ++i) maxi = max(maxi, arr[i]);
  return maxi;
}
long long min_arr(long long arr[], long long n) {
  long long maxi = INF;
  for (int i = 0; i < n; ++i) maxi = min(maxi, arr[i]);
  return maxi;
}
struct triple {
  long long a, b, c;
  triple(long long x, long long y, long long z) {
    a = x;
    b = y;
    c = z;
  }
  triple() {
    a = 0;
    b = 0;
    c = 0;
  }
  bool operator<(const triple *x) { return a < x->a; }
  bool operator==(const triple *x) {
    return a == x->a and b == x->b and c == x->c;
  }
  bool operator>(const triple *x) { return a > x->a; }
};
bool f(int a, int i) { return ((a >> i) & 1); }
long long mex(vector<long long> &kek) {
  vector<long long> cnt(kek.size() + 100);
  for (int i = 0; i < kek.size(); ++i) {
    ++cnt[kek[i]];
  }
  for (int i = 0; i < cnt.size(); ++i) {
    if (cnt[i] == 0) return i;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  map<string, long long> ss[n];
  map<string, long long> com;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < s.size(); ++j) {
      string now;
      for (long long k = j; k < s.size(); ++k) {
        now += s[k];
        ss[i][now]++;
        com[now]++;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    string ans = "000000000000000";
    for (auto kek = ss[i].begin(); kek != ss[i].end(); ++kek) {
      if (kek->second == com[kek->first]) {
        if (kek->first.size() < ans.size()) ans = kek->first;
      }
    }
    cout << ans << '\n';
  }
}

### Prompt

Your task is to create a cpp solution to the following problem:

There are n phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.

There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then:

  * if he enters 00 two numbers will show up: 100000000 and 100123456, 
  * if he enters 123 two numbers will show up 123456789 and 100123456, 
  * if he enters 01 there will be only one number 100123456. 



For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number.

Input

The first line contains single integer n (1 ≤ n ≤ 70000) — the total number of phone contacts in Polycarp's contacts.

The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct.

Output

Print exactly n lines: the i-th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the i-th number from the contacts. If there are several such sequences, print any of them.

Examples

Input

3
123456789
100000000
100123456


Output

9
000
01


Input

4
123456789
193456789
134567819
934567891


Output

2
193
81
91

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct point {
  long double x, y;
  point() {
    x = 0;
    y = 0;
  }
  point(long long a, long long b) {
    x = a;
    y = b;
  }
  bool operator==(const point &b) { return x == b.x and y == b.y; }
  bool operator>(const point &b) {
    if (x > b.x) return true;
    if (x < b.x) return false;
    if (x == b.x) {
      if (y < b.y) return false;
      if (y > b.y) return true;
      return true;
    }
  }
  bool operator<(point &b) { return (b > point(x, y)); }
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist(point b) {
    return sqrt((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  long double dist_kv(point b) {
    return ((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  bool point_on_sig(point &a, point &b) {
    return abs(a.dist(b) - (dist(a) + dist(b))) <= 1e-6;
  }
  long double polar_angle() {
    long double alpha = atan2(y, x);
    long double pi = 3.141592654;
    if (alpha < 0) alpha += 2 * pi;
    return alpha;
  }
};
struct line {
  long double A, B, C;
  line() {
    A = 0;
    B = 0;
    C = 0;
  }
  line(point &a, point &b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = -A * a.x - B * a.y;
  }
  line(long double a, long double b, long double c) {
    A = a;
    B = b;
    C = c;
  }
  line line_perp_dan_cherez_point(point a) {
    return line(-B, A, -(A * a.y) + B * a.x);
  }
  bool onli(point a) { return A * a.x + B * a.y + C == 0; }
  point intersect_lines(line &a) {
    point p;
    p.x = -(((C * a.B) - (a.C * B)) / ((A * a.B) - (a.A * B)));
    p.y = -(((A * a.C) - (a.A * C)) / ((A * a.B) - (a.A * B)));
    return p;
  }
  bool intersect(line &b) { return A * b.B - B * b.A != 0; }
  bool operator==(line &a) { return A == a.A && B == a.B && C == a.C; }
  long double distance_perpendicular(point &d) {
    return abs(A * d.x + B * d.y + C) / (sqrt(A * A + B * B));
  }
};
struct vc {
  long double x, y;
  vc() {
    x = 0;
    y = 0;
  }
  vc(long double x_, long double y_) {
    x = x_;
    y = y_;
  }
  vc(const point &a) {
    x = a.x;
    y = a.y;
  }
  vc minus(const vc &b) { return vc(x - b.x, y - b.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double scalar(const vc &b) { return x * b.x + y * b.y; }
  long double vector(const vc &b) { return x * b.y - y * b.x; }
  long double angle(const vc &b) { return atan2(vector(b), scalar(b)); }
};
vector<int> top;
void top_sort(int v, vector<int> nodes[], int used[], int colors[]) {
  if (colors[v] == 1) {
    cout << -1;
    exit(0);
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (used[nodes[v][i]] == 0) top_sort(nodes[v][i], nodes, used, colors);
  }
  top.push_back(v + 1);
  used[v] = 1;
  colors[v] = 2;
}
vector<int> z_function(string s) {
  vector<int> z(s.size());
  for (int i = 1, l = 0, r = 0; i < s.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
vector<int> p_function(string s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}
vector<int> now_ans;
void dfsik(int v, vector<int> nodes[], int colors[], int turn) {
  if (colors[v] == 1) {
    now_ans.push_back(0);
    return;
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (turn == 1)
      dfsik(nodes[v][i], nodes, colors, 2);
    else
      dfsik(nodes[v][i], nodes, colors, 1);
  }
  if (nodes[v].empty()) {
    now_ans.push_back(turn);
    return;
  }
  colors[v] = 2;
}
long long t[8 * 100000];
long long t1[8 * 100000];
long long a[8 * 100000];
void push(long long v, long long l, long long r) {
  if (a[v] == 0) return;
  if (l != r) {
    a[v * 2] += a[v];
    a[v * 2 + 1] += a[v];
  }
  t[v] += a[v] * (r - l + 1);
  t1[v] += a[v];
  a[v] = 0;
}
void build(long long a[], long long v, long long tl, long long tr) {
  if (tl == tr) {
    t[v] = a[tl];
    t1[v] = a[tl];
  } else {
    long long tmtm = (tl + tr) / 2;
    build(a, v * 2, tl, tmtm);
    build(a, v * 2 + 1, tmtm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
    t1[v] = max(t1[v * 2], t1[v * 2 + 1]);
  }
}
long long sum(long long v, long long tl, long long tr, long long l, long long r,
              long long num) {
  if (l > r) return 0;
  push(v, tl, tr);
  if (l == tl && r == tr) {
    t[v] += num;
    t1[v] += num;
    return t[v];
  }
  if (l <= tl and tr <= r) {
    a[v] += num;
    push(v, tl, tr);
    return t[v];
  }
  long long tmtm = (tl + tr) / 2;
  return (sum(v * 2, tl, tmtm, l, min(r, tmtm), num) +
          sum(v * 2 + 1, tmtm + 1, tr, max(l, tmtm + 1), r, num));
}
long long maxim(long long v, long long tl, long long tr, long long l,
                long long r) {
  if (l > r) return -LONG_LONG_MAX;
  push(v, tl, tr);
  if (l == tl && r == tr) return t1[v];
  long long tmtm = (tl + tr) / 2;
  return max(maxim(v * 2, tl, tmtm, l, min(r, tmtm)),
             maxim(v * 2 + 1, tmtm + 1, tr, max(l, tmtm + 1), r));
}
void sett(long long v, long long idx, long long x, long long l, long long r) {
  if (l == r) {
    t[v] = x;
    t1[v] = x;
    return;
  }
  long long m = (l + r) >> 1;
  if (l <= idx and m >= idx) {
    sett(2 * v, idx, x, l, m);
  } else
    sett(2 * v + 1, idx, x, m + 1, r);
  t[v] = min(t[2 * v], t[2 * v + 1]);
  t1[v] = max(t1[2 * v], t1[2 * v + 1]);
}
int parents[500000];
void create(int v) { parents[v] = v; }
int find_parent(int v) {
  if (v == parents[v]) return v;
  return parents[v] = find_parent(parents[v]);
}
void join(int a, int b) {
  int x = find_parent(a);
  int y = find_parent(b);
  if (x != y) {
    parents[x] = y;
  }
}
vector<long long> manac(string s, int shift) {
  long long l = 0;
  long long r = -1;
  long long n = s.size();
  vector<long long> ans(n);
  for (int i = 1; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i + shift, ans[r - i + l + shift]);
    }
    while (i - k - 1 >= 0 && i + k + 1 - shift < n &&
           s[i - k - 1] == s[i + k + 1 - shift]) {
      k++;
    }
    if (i + k - shift > r) {
      l = i - k;
      r = i + k - shift;
    }
    ans[i] = k;
  }
  return ans;
}
long long INF = (long long)1e20;
vector<int> dividers(int x) {
  vector<int> ans;
  ans.push_back(x);
  for (int i = 2; i <= sqrt(x); ++i) {
    if (x % i == 0) {
      ans.push_back(i);
      if (i != sqrt(x)) ans.push_back(x / i);
    }
  }
  return ans;
}
long long max_arr(long long arr[], long long n) {
  long long maxi = -INF;
  for (int i = 0; i < n; ++i) maxi = max(maxi, arr[i]);
  return maxi;
}
long long min_arr(long long arr[], long long n) {
  long long maxi = INF;
  for (int i = 0; i < n; ++i) maxi = min(maxi, arr[i]);
  return maxi;
}
struct triple {
  long long a, b, c;
  triple(long long x, long long y, long long z) {
    a = x;
    b = y;
    c = z;
  }
  triple() {
    a = 0;
    b = 0;
    c = 0;
  }
  bool operator<(const triple *x) { return a < x->a; }
  bool operator==(const triple *x) {
    return a == x->a and b == x->b and c == x->c;
  }
  bool operator>(const triple *x) { return a > x->a; }
};
bool f(int a, int i) { return ((a >> i) & 1); }
long long mex(vector<long long> &kek) {
  vector<long long> cnt(kek.size() + 100);
  for (int i = 0; i < kek.size(); ++i) {
    ++cnt[kek[i]];
  }
  for (int i = 0; i < cnt.size(); ++i) {
    if (cnt[i] == 0) return i;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  map<string, long long> ss[n];
  map<string, long long> com;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < s.size(); ++j) {
      string now;
      for (long long k = j; k < s.size(); ++k) {
        now += s[k];
        ss[i][now]++;
        com[now]++;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    string ans = "000000000000000";
    for (auto kek = ss[i].begin(); kek != ss[i].end(); ++kek) {
      if (kek->second == com[kek->first]) {
        if (kek->first.size() < ans.size()) ans = kek->first;
      }
    }
    cout << ans << '\n';
  }
}

```